题目描述

原题链接：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. 打家劫舍