代码随想录算法训练营第三十九天-动态规划-198. 打家劫舍

• 动规五部曲
  • dp[i]表示在下标为i的房间偷或不偷与前面所偷之和所能获得的最大价值
  • 递推公式：dp[i] = std::max(dp[i - 2] + nums[i], dp[i - 1])
  • 初始化：要给dp[0]与dp[1]来给定初始值，因为递推公式有-1与-2。dp[0] = nums[0], dp[1] = std::max(nums[0], nums[1]);
    • 其它下标值，初始成任意值都可以，因为其值是由前面元素推导出来的
  • 遍历顺序：从2开始到最后一个房间的下标
  • 打印

class Solution {
public:int rob(vector<int>& nums) {int dp[nums.size()];memset(dp, 0, sizeof(dp));if (nums.size() == 1) return nums.at(0);dp[0] = nums.at(0);dp[1] = std::max(dp[0], nums.at(1));for (int i = 2; i < nums.size(); i++) {dp[i] = std::max(dp[i - 1], dp[i - 2] + nums.at(i));}return dp[nums.size() - 1];}
};

• 汇总