【学会动态规划】打家劫舍 II（12）

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：213. 打家劫舍 II - 力扣（Leetcode）

这道题目也不难理解，

他和打家劫舍第一个版本只有一个差别，就是他的首尾是相连的，

其他的条件都是一致的。

那我们其实可以分析一下，我们能把这道题目转换成打家劫舍第一个版本吗？

如果我们偷0位置，那1位置就不能偷，那我们的2~n-2位置，就能为所欲为

如果我们不偷0位置，那我们1~n-1的位置就能为所欲为（转换成打家劫舍I）

所以最后返回的值就是这两种情况的最大值。

2. 算法原理

1. 状态表示

f [ i ] 表示偷到 i 位置时，偷 nums[ i ]，此时的最大金额

g [ i ] 表示偷到 i 位置时，不偷 nums[ i ]，此时的最大金额

2. 状态转移方程                

根据我们的状态表示，我们可以得出：

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

g [ i ] = max( f [ i - 1 ]，g [ i - 1 ] )

3. 初始化

f [ 0 ] = num[ 0 ]， g [ 0 ] = 0

4. 填表顺序

从左往右

5. 返回值

max( f [ n - 1 ]，g [ n - 1 ] )

3. 代码编写

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        return max(nums[0] + rob1(nums, 2, n - 2) , rob1(nums, 1, n - 1));
    }
private:
    int rob1(const vector<int>& nums, int start, int n) {
        if(start > n) return 0;
        int size = nums.size();
        vector<int> f(size);
        auto g = f;
        f[start] = nums[start];
        for(int i = start + 1; i <= n; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1], g[i - 1]);
        } 
        return max(f[n], g[n]);
    }
};

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~