我的算法时间记录二我的算法时间记录二

二、动态规划类

2020.8.15 小杨缓慢但前进

爬楼梯：

文章图片

先进思想：
开始我想的递归是一个时间复杂度在2的阶乘级别，超出时间限制，是因为里面有很多的重复计算。递归不是不能用，在重复的这块进行优化就可以，把计算过的存储起来，遇到就直接查。后来我采用的动态规划，开始填一维表，时间复杂度是减下来了，但仍然存在空间上的优化。可以直接使用两个变量，一步步的赋值。仅采用常数级别的空间。
本来我以为到此就为止了，这个题印出来非常厉害的数学解法。根据递推式写出矩阵相乘的形式，就能直接求出f(n)的表达式，其中涉及如下矩阵运算，通过对角化满秩矩阵将矩阵的N次方转化为对角矩阵的n次方，而对角矩阵的n次方直接等于对角线上的元素的n次方，一下子就简化不少：

文章图片

文章图片

在这里，我们可以直接用数学公式去求解，一步到位，一行代码中的pow运算会有logn级别的时间复杂度，因此时间复杂度被降低到logn级别，空间复杂度是常数级别。我们发现，在前期做越多的数学分析，就能更大程度地降低问题复杂度。也就是人帮机器解决的问题越多，人的思考越多，机器的“思考”就能越少，就越高效。
动态规划类的题目一般都能写成这种递推式，递推式的只要是线性的（非线性也能转化为线性，只需要变化一下函数，加个常量啥的），就能使用这种数学思路求解。在编程实现上，由于具备连续性，因此可以不用开辟新数组，而是用常数个变量进行滚动赋值即可，但是要十分注意变量赋值的顺序。

打家劫舍：

文章图片

先进思想：
还是那个经典的动态规划方法，就是填表法。格外注意一下特殊值的返回和初始值的设置。
另外有一种新思路，就是针对这种可以“滚动”的数值变化，我们可以使用两个单变量来互相更新，first变量的当前值是second的前一个值，我本身使用的是原数组的更新，不需要额外的空间。

区域和检索：

【我的算法时间记录二】

文章图片

先进思想：
一开始没写过这种类，就直接看答案了，这个的意思是初始化在创建对象的时候就要懂点脑筋，因为sumrange函数需要被调用多次，如果初始化的时候仅仅是单纯的初始化，将对象和nums数组联系起来的话就会导致sumrange函数多次使用消耗的时间资源和空间资源过大。因此在初始化的时候，就要构建利于sumrange计算的数据结构。本题中求区间和，那么就可以构建一个累计和的列表，这里用到动态规划的思想。

除数博弈：

文章图片

先进思想：
感觉这是个博大精深的数学问题，就列举了一些情况之后没做大胆猜测。后来看到那一行代码，我觉得有点可惜。看了题解的证明之后，心服口服。首先我们通过找规律可以发现，当N是偶数的时候，先手胜；当N是奇数的时候，先手败。下面用数学归纳法证明。
(1)假设N<=k时，当N是偶数的时候，先手胜；当N是奇数的时候，先手败。
(2)讨论N=k+1的情况：
当k+1为奇数时，对于先手Alice来说，这时候选的因数只能是奇数（因此这个先手其实是没有优势的），因此导致下一个N必为偶数（奇数-奇数）。此时Bob成了先手，而此时的N<=k了，满足(1)中条件，这个时候的先手Bob必胜。
当k+1为奇数时，对于先手Alice来说，这时候因数是可能为奇或者为偶的，因此有了选择的余地，当然一定要选自己能赢的选择。选择一次之后，肯定满足（1）中条件，因此可以利用（1）中结论让自己必赢。只需要选偶数因数，使得下一个N为奇数，从而使得此时的先手Bob必败。