动规算法题：打家劫舍Ⅱ

二肥是只大懒蓝猫

发布于 2023-10-13 11:42:46

1020

发布于 2023-10-13 11:42:46

文章被收录于专栏：热爱C嘎嘎热爱C嘎嘎

题目链接：打家劫舍Ⅱ

题目分析

状态表示

从题目分析中可以得知，是有偷和不偷的情况，因此根据做题经验，就使用两个数组来对应着两个情况。

状态转移方程

①当选择偷第i个位置，那就意味着第i-1个位置的值是不能偷的（从左往右算）。而不去选择第i-1个位置，那就是g[i-1]，因此，f[i]的状态转移方程是：

f[i] = g[i-1]+nums[0];

②当选择不偷第i个位置，那就意味着第i-1个位置是可以偷，但是也可以不偷，因此需要选择这两者其中的最大值，因此，g[i]的状态转移方程是：

g[i] = max(g[i-1],f[i-1]);//在偷和不偷两种中选择最大值

初始化

从状态转移方程中可以知道，我们需要从i =1出发，为了不越界，需要将i==0这个位置初始化。因为f[i]是偷的，那么将f[0] = nums[0]，g[i]不偷，则g[0] = 0；

方向是从左到右开始计算结果。

返回值

在到达最后的位置，有两种选择，一是不偷，二是偷，因此最终结果是在这两种情况下，选择最大值的：

return max(f[n-1],g[n-1]);

编写代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();/*获取数组的长度*/
        return max(nums[0]+robl(nums,2,n-2),robl(nums,1,n-1));/*在偷和不偷中选择最大值*/
    }
    int robl(vector<int>& nums,int left,int right)
    {
        if(left > right) return 0;
        /*创建出dp数组:g和f*/
        int n = nums.size();
        vector<int> f(n);
        auto g =f;
        /*初始化*/
        f[left] = nums[left];
        g[left] = 0;/*其实在创建的时候，就已经有了，写出来是方便看*/
        /*开始填值，从左到右*/
        for(int i = left+1;i<=right;++i)
        {
            f[i] = g[i-1]+nums[i];
            g[i] = max(g[i-1],f[i-1]);
        }

        return max(g[right],f[right]);
    }
};