二、动态规划类

2020.8.15 小杨缓慢但前进 

• 爬楼梯 ：

先进思想：

开始我想的递归是一个时间复杂度在2的阶乘级别，超出时间限制，是因为里面有很多的重复计算。递归不是不能用，在重复的这块进行优化就可以，把计算过的存储起来，遇到就直接查。后来我采用的动态规划，开始填一维表，时间复杂度是减下来了，但仍然存在空间上的优化。可以直接使用两个变量，一步步的赋值。仅采用常数级别的空间。

本来我以为到此就为止了，这个题印出来非常厉害的数学解法。根据递推式写出矩阵相乘的形式，就能直接求出f(n)的表达式，其中涉及如下矩阵运算，通过对角化满秩矩阵将矩阵的N次方转化为对角矩阵的n次方，而对角矩阵的n次方直接等于对角线上的元素的n次方，一下子就简化不少：

在这里，我们可以直接用数学公式去求解，一步到位，一行代码中的pow运算会有logn级别的时间复杂度，因此时间复杂度被降低到logn级别，空间复杂度是常数级别。我们发现，在前期做越多的数学分析，就能更大程度地降低问题复杂度。

动态规划类的题目一般都能写成这种递推式，递推式的只要是线性的（非线性也能转化为线性，只需要变化一下函数，加个常量啥的），就能使用这种数学思路求解。在编程实现上，由于具备连续性，因此可以不用开辟新数组，而是用常数个变量进行滚动赋值即可，但是要十分注意变量赋值的顺序。

• 打家劫舍：

先进思想：

还是那个经典的动态规划方法，就是填表法。格外注意一下特殊值的返回和初始值的设置。

另外有一种新思路，就是针对这种可以“滚动”的数值变化，我们可以使用两个单变量来互相更新，first变量的当前值是second的前一个值，我本身使用的是原数组的更新，不需要额外的空间。