代码随想录第42天|动态规划

参考

1. dp[j] 表示偷盗的总金额, j 表示前 j 间房(包括j)的总偷盗金额
2. 
3. 初始化: dp[0] 一定要偷, dp[1] 则取房间0,1的最大值
4. 遍历顺序: 从小到大

class Solution {
public:int rob(vector<int>& nums) {if (nums.size() < 2) {return nums[0];}vector<int> dp(nums.size(), 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];}
};

分情况讨论

1. 包含首元素, 不含尾元素
2. 不包首元素, 含尾元素
3. (不包首元素, 不包尾元素在情况1,2中)

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

无法使用层序遍历转换成一维数组, 比如下面最大值为 5

后续重做