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

发布时间:2024年01月14日

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];
    }
}

问题1:为什么dp数组长度定义为 n + 2呢?

因为dp[i] 与dp[i+2] 和dp[i+1]有关,为了防止数组越界,将数组长度定为n+2


如果有什么不明白或者文章中内容有误,请在评论区留言。我看到后会一一回复。

及时收获反馈,这对我很重要。

文章来源:https://blog.csdn.net/From_C/article/details/135580897
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。