【学会动态规划】打家劫舍 II（12）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学会动态规划】打家劫舍 II（12）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

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

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

1. 题目解析

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

【学会动态规划】打家劫舍 II（12）,学会动态规划,动态规划,算法,学习,c++

这道题目也不难理解，

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

其他的条件都是一致的。

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

如果我们偷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]);
    }
};