万物的开始，首先介绍一下动态规划（dynamic programming，DP）的基本概念：动态规划适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法耗费时间远远少于朴素解法。
动态规划总共可以分为4个步骤：1、定义子问题 2、写出子问题的递推关系 3、确定DP数组的计算顺序。4、空间优化。
步骤1：子问题与原问题相似，但是规模很小。子问题是参数化的，假设定义的子问题中参数为k。假设有n个房子，总共有n个子问题。动态规划实际上就是通过求解一堆子问题的解，来找出原问题的解。一个子问题的解是可以通过其他子问题的解求出。例如这道小偷问题中，f(k) 可以由 f(k - 1)和f(k - 2)求出。
步骤2：写出子问题的递推关系。设置有k间房子，那么偷k个房子，则有2种偷法，要不第k间房子被偷，要不第k-1间房子被偷。注意在写，递推关系的时候，写上边界情况，比如k = 0,k = 1的值。
步骤3：确定DP数组的计算顺序。此外，动态规划有自底向上和自顶向下两种解决问题的方法，自顶向下是记忆化（备忘录）递归，自底向上是递推、使用DP数组的循环方法。DP 数组也可以叫”子问题数组”，那么，只要搞清楚了子问题的计算顺序，就可以确定 DP 数组的计算顺序。对于小偷问题，我们分析子问题的依赖关系，发现每个f(k) 依赖 f(k -1) 和 f(k - 2)。也就是说， dp[k] 依赖 dp[k-1] 和 dp[k-2]。
步骤4：空间优化的基本原理是，很多时候并不需要始终持有全部的 DP数组。对于小偷问题，我们发现，最后一步计算 f(n)的时候实际上只用到了 f(n-1)和 f(n- 2)的结果，n- 3之前的子问题，实际上早就已经用不到了。那么，可以只用两个变量保存两个子问题的结果，就可以依次计算出所有的子问题。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution { public int rob(int[] nums) { // 长度为空 if(nums.length == 0) return 0; int N = nums.length; int[] dp = new int[N+1]; dp[0] = 0; dp[1] = nums[0]; for(int k = 2;k dp[k] = Math.max(dp[k-1],nums[k-1] + dp[k-2]); } return dp[N]; }} |