本来在做了几天的动态规划（Dynamic Programming，DP）,这道EZ难度的动规题应该是手到擒来的。但实际在做的时候，突然有个小的地方纠结了一下。所以还是决定记录一下这道题的思考过程。
动态规划在给定约束条件下，优化某种指标时（最常见的是最值），有着很好的效果。当问题可以分解成离散子问题，并且子问题相互独立时DP（最优子结构），能够采用动态规划的方法。此外，当子问题有重叠时（重叠子问题），利用备忘录（memo）或者"DP table"能够提高穷举效率。
上段已经提到了动态规划的两个要素，那么DP最后一个要素就是“状态转移方程”。可以说上述两个要素可以说是判断能否/高效使用动态规划算法的条件，而第三个要素则是DP的灵魂,也是在做题过程中DP的难点所在。
那么如何写出状态转移方程？其实在这几天的DP专题刷题中，我也是有所收获。写状态转移方程的过程，其实和我们高中时做数学归纳的题目很像。回忆一下我们是如何使用数学归纳法的：1.证明当n=1时命题成立；2.假设n=m时命题成立，那么可以推导出在n=m+1时命题也成立。将数学归纳法的思想类比到DP的状态转移方程，那么写状态转移方程要考虑一下几点：1.这个问题的最简单情况是啥（base case,边界条件），比如这道题nums数组长度为0时，返回0，长度为1时，返回nums[0]，长度为2时返回max(nums[0], nums[1])。2.类比数学归纳法，如何从n=m状态转变成n=m+1状态，并且在状态转变过程中要进行什么选择。例如本题中dp[i] = max(dp[i-2]+nums[i], dp[i-1]); 3.结合题目要求对dp数组的值进行选取，这题是直接采用dp[len-1]，有的题则是max/min(dp[i])。
回到本道题，见下图。这题纠结我的一处是，在写状态转移方程时，我一开始写的是对的😂dp[i] = max(dp[i-2]+nums[i], dp[i-1])，后面纠结了一下，改成了 dp[i] = max(dp[i-1] , max( dp[0], dp[1], dp[2], ... dp[i-2]) + nums[i])。因为小偷也可能比如直接跳过两家去第三家偷。后面思考了一下，dp[k]一定>=dp[k-1],那么我的考虑也就多余了，但我觉得这个思考还是有意义的。
那么将以上想法转换为代码可以写成(贴代码发现发布后会有符号字母出错，还是上图吧，我服了🙃。还是学习一下markdown吧)：
再对空间复杂度进行优化，将空间复杂度从O(n)->O(1):
