确定用作状态转移的dp数组的下标及含义 dp[i] 考虑下标i(包含i)之前偷到的最多的金币
动规核心 状态转移方程/递推公式
偷i dp[i-2]+nums[i]
不偷i dp[i-1] 此时i-1处可能偷也可能不偷
dp[i] = max(dp[i-2]+nums[i], dp[i-1])
dp数组如何初始化 dp[0]=nums[0] dp[1]=max(nums[0], nums[1])
// dp[j] 截止j号房屋前偷到的最高金额
// 偷当前 dp[j-2]+nums[j]
// 不偷当前 dp[j-1]
// dp[j] = max(dp[j-2]+nums[j], dp[j-1])
class Solution {
public:
int rob(std::vector<int>& nums) {
// 错误 长度为1要单独讨论 下面用到nums[1]
if (nums.size()==1) return nums[0];
std::vector<int> dp(nums.size());
dp[0]=nums[0], dp[1]=std::max(nums[0], nums[1]);
for (int j=2;j<nums.size();j++){
dp[j] = std::max(dp[j-2]+nums[j], dp[j-1]);
}
return dp[nums.size()-1];
}
};