C/C++教程

Leetcode-打家劫舍问题汇总-动态规划

本文主要是介绍Leetcode-打家劫舍问题汇总-动态规划,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述

1.打家劫舍Ⅰ
在这里插入图片描述
解题思路

  • 考虑特殊情况:
    –当只有一间房时,ans=nums[0];
    – 当有两间房时,ans=max(nums[0],nums[1]);因为前两间房相邻,只能偷一家;
  • 一般情况,即房间数>2时,此时用dp[i]表示前i间房的最大价值,对于第k间房:
    –偷,dp[k]=dp[k-2]+nums[k];
    –不偷,dp[k]=dp[k-1];
  • 所以有状态转移方程:dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
    代码展示
class Solution {
public:
/*
dp[i]表示窃取前i间房可取得的最大价值
与dp[i-2]+num[i],dp[i-1]
*/  
    int dp[105];
    int rob(vector<int>& nums) {
        int l=nums.size();
        if(l<2)return nums[0];
        dp[0]=nums[0],dp[1]=max(nums[0],nums[1]);
        for(int i=2;i<l;i++){
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[l-1];
    }
};

2.打家劫舍Ⅱ
解题思路
在这里插入图片描述

  • 这题与Ⅰ的唯一不同就是第一间房与最后一间房相邻,即不能同时选择nums[0]与nums[l-1];
  • 分析:
    –可以把数组分成两个区间[0,n-2],[2,n-1],求这两部分时不需要考虑首位相邻问题;1
    –考虑一种特殊情况:
    在这里插入图片描述
    代码展示
class Solution {
public:
/*
1.按照Ⅰ方法进行,可能会有同时选择0,l-1的情况
2.判断两个特殊情况:偷了第一家->第n家不能偷
                  
*/
    int Dp(vector<int>& nums,int l,int r){
        int f1=nums[l],f2=max(nums[l],nums[l+1]);
        for(int i=l+2;i<=r;i++){
            int temp=max(f2,f1+nums[i]);
            f1=f2;
            f2=temp;
        }
        return f2;
    }
    int rob(vector<int>& nums) {
        int l=nums.size();
        if(l==1)return nums[0];
        if(l==2)return max(nums[0],nums[1]);
        return max(Dp(nums,0,l-2),Dp(nums,1,l-1));
    }
};

在这里插入图片描述
3.打家劫舍Ⅲ
在这里插入图片描述
解题思路
(待更新~)

代码展示


  1. 因为首尾必然不能同时选择 ↩︎

这篇关于Leetcode-打家劫舍问题汇总-动态规划的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!