原题

LeetCode 198. 打家劫舍

思路

• 从头开始遍历，用一个dp[n][2]的数组来记录遍历到当前房屋时能够偷窃到的最高金额。
• dp[i][0]代表不偷第i间房屋能够获得的最高金额，即dp[i-1][0]，dp[i-1][1]中最大的那一个。
• dp[i][1]代表偷第i间房屋能够获得的最高金额，那么肯定为第i-1间房屋不能偷获取到的最高金额+第i间房屋的金额，即dp[i-1][0] + nums[i]。
• 最后能偷到的最大的金额就是dp[n-1][0]和dp[n-1][1]中最大的那一个。

代码

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

运行截图

收获