动态规划篇-03：打家劫舍

198、打家劫舍

状态转移方程

base case

边界问题就是：走到最后一间房子门口也没抢，那么最终抢到的金额为0

明确状态

“原问题和子问题中会变化的变量”

抢到的金额数就是状态，因为随着在每一件房子门口做选择，抢到的金额数会随之变化

确定选择

“导致状态变化的行为”

在每间房子门口都可以做出两个选择：“抢”或者“不抢”。如果抢了的话那么下一间就不能抢，如果这件不抢的话下一间就可以抢

定义dp函数

根据题意，定义dp(n) 为：n间房子能抢到的最大金额数

此外，还要考虑从第几间房子开始抢。那么dp函数应该有两个参数：从第几间房子开始-start，可抢的房子数组-nums

那么状态转移方程就是：

dp(nums,start) = Math.max(nums[start] + dp(nums,start + 2),
                    dp(nums,start + 1));
//nums[start] + dp(nums,start + 2    表示从第start家开始抢，抢到的金额自然是第start家的金额
//加上从start+2家开始抢得到的金额
//dp(nums,start + 1) 表示第start家不抢了，从下一家开始抢

我们可以看到，这里再次体现了

“[分解问题]的思路可以扩展成动态规划算法。”

我们把“从第start间房子开始抢到的金额”这个问题分解为：“从下下间房子开始抢” 和 “从下一间房子开始抢” 两个子问题

有了状态转移方程，我们就可以写出最基础的暴力递归解法了

暴力递归

class Solution {
    public int rob(int[] nums) {
        return dp(nums,0);
    }
    /*dp函数表示从第 start 间房子开始抢的最大金额*/
    int dp(int[] nums,int start){
        /*如果这排房子从头到尾都挑完了还没开始抢，那就什么也抢不到*/
        //base case
        if(start >= nums.length){
            return 0;
        }
        
        /*在每个房子门前有两种选择，抢 / 不抢*/
        int res = Math.max(nums[start] + dp(nums,start+2)
                , dp(nums,start+1));
        return res;
    }
}

这种解法显然时间复杂度太高。按照我们之前所讲的：通过处理“重叠子问题”来降低时间复杂度

使用了备忘录的从上到下的递归解法

class Solution {
    public int rob(int[] nums) {
        int[] memo = new int[nums.length];
        //初始化备忘录数组
        Arrays.fill(memo,-1);
        return dp(nums,0,memo);
    }
    int dp(int[] nums,int start,int[] memo){
        //base case
        if(start >= nums.length){
            return 0;
        }
        //如果备忘录中存有这个数值，就直接取用
        if(memo[start] != -1){
            return memo[start];
        }
        //状态转移方程
        memo[start] = Math.max(dp(nums,start+1,memo),
                nums[start] + dp(nums,start+2,memo));
        return memo[start];
    }
}

问题1：如何判断该问题是否能够优化？

根据前面的文章我们已将知道：我们可以通过优化“重叠子问题”来降低时间复杂度。那么我们怎么才能知道是否存在“重叠子问题”呢？

抽象出递归框架，先找出 [状态] ，然后根据递归框架看看：如果从一个状态转移到另一个状态有不止一条路径，那么说明存在 [重叠子问题]

使用了dp数组的从下到上的迭代解法

class Solution {
    /*从下到上的迭代数组解法*/
    public int rob(int[] nums) {
        int n = nums.length;
        //为什么数组长度定义为 n+2？
        /*dp[i] 表示从第 i 家开始抢劫获得的金额数，0~n*/
        int dp[] = new int[n + 2];

        for (int i = n-1; i >= 0; i--) {
            dp[i] = Math.max(nums[i] + dp[i+2],
                    dp[i+1]);
        }
        return dp[0];
    }
}