题目描述

原题链接：198. 打家劫舍

解题思路

• 动态规划五步曲：

（1）dp[i]含义： 从0-i中选择数，组成的最大总和。

（2）递推公式： dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])，因此相邻的数不能选择，最少隔一个选一个。dp[i - 1]：不选当前的i，选择上一个i-1,。dp[i - 2] + nums[i]：从上一个i - 2往后选择当前i，而不选择上一个i - 1。

（3）dp数组初始化： dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。

（4）遍历顺序： 因为有i-1和i-2，因此从i=2开始遍历，一直到n-1（因为这次设置dp[0]具有一个含义，因此到n-1，而不是n）。

（5）举例：

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1)          return nums[0];
        int dp[101] = {0};
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < nums.size(); i++) {
            // 在不选当前的物品选择了前一个物品和选择当前物品中找出一个最大情况
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[nums.size() - 1];
    }
};

参考文章：198. 打家劫舍

最后

以上就是个性机器猫为你收集整理的163、【动态规划】leetcode ——198. 打家劫舍（C++版本）题目描述解题思路的全部内容，希望文章能够帮你解决163、【动态规划】leetcode ——198. 打家劫舍（C++版本）题目描述解题思路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。