威海经区建设局网站,广告推广精准引流,杭州网站开发平均工资,网站开发公司基本业务流程图198.打家劫舍 参考
dp[j] 表示偷盗的总金额, j 表示前 j 间房(包括j)的总偷盗金额初始化: dp[0] 一定要偷, dp[1] 则取房间0,1的最大值遍历顺序: 从小到大
class Solution {
public:int rob(vectorint nums) {if (nums.size() 2) {return nums[0];}vectorint nums) {if (nums.size() 2) {return nums[0];}vectorint 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];}
};213.打家劫舍II 分情况讨论
包含首元素, 不含尾元素不包首元素, 含尾元素(不包首元素, 不包尾元素在情况1,2中)
class Solution {
public:int rob(vectorint 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(vectorint nums, int begin, int end) {if ((end - begin 1) 2) return max(nums[begin], nums[end]);vectorint 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];}
};337. 打家劫舍 III 无法使用层序遍历转换成一维数组, 比如下面最大值为 5 后续重做
