男子做网站,网站制作需求,seo网站推广软件,提供网站建设出售题目来源#xff1a;https://leetcode.cn/problems/house-robber/description/ C题解#xff1a;因为是间接偷窃#xff0c;所以偷nums[i]家前#xff0c;一定偷过第i-2或者i-3家#xff0c;因为i-1不能偷。
例如12345共5家#xff0c;先偷第1家#xff0c;那么2不能偷…题目来源https://leetcode.cn/problems/house-robber/description/ C题解因为是间接偷窃所以偷nums[i]家前一定偷过第i-2或者i-3家因为i-1不能偷。
例如12345共5家先偷第1家那么2不能偷如果偷5那肯定偷3所以只在3和4之间作判断就行。即跳跃为2或3步。dp[i] max(dp[i-2]nums[i-1], dp[i-3]nums[i-1]);
class Solution {
public:int rob(vectorint nums) {int len nums.size();if(len 1) return nums[0];vectorint dp(len1, 0); // 在前i家偷到的最大金额dp[0] 0;dp[1] nums[0];dp[2] nums[1];for(int i 3; i len; i) {dp[i] max(dp[i-2]nums[i-1], dp[i-3]nums[i-1]);}return max(dp[len], dp[len-1]);}
};
代码随想录题解
class Solution {
public:int rob(vectorint nums) {if (nums.size() 0) return 0;if (nums.size() 1) return nums[0];vectorint dp(nums.size());dp[0] nums[0];dp[1] max(nums[0], nums[1]);for (int i 2; i nums.size(); i) {dp[i] max(dp[i - 2] nums[i], dp[i - 1]);}return dp[nums.size() - 1];}
};
