今天就是打家劫舍的一天,微笑
198.打家劫舍
leetcode題目鏈接
視頻講解
文章講解
動規五部曲分析如下：
-
確定dp數組（dp table）以及下標的含義
dp[i]：考慮下標i（包括i）以內的房屋，最多可以偷竊的金額為dp[i]。 -
確定遞推公式
決定dp[i]的因素就是第i房間偷還是不偷。
如果偷第i房間，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考慮的，找出 下標i-2（包括i-2）以內的房屋，最多可以偷竊的金額為dp[i-2] 加上第i房間偷到的錢。
如果不偷第i房間，那么dp[i] = dp[i - 1]，即考 慮i-1房，（注意這里是考慮，并不是一定要偷i-1房，這是很多同學容易混淆的點）
然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
- dp數組如何初始化
從遞推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，遞推公式的基礎就是dp[0] 和 dp[1]
從dp[i]的定義上來講，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);
class Solution {
public:int rob(vector<int>& nums) {//1. dp數組的含義 是dp[i] 0到i，的最優選項，不一定包含當前節點vector<int> dp(nums.size(), 0);if(nums.size() == 0) return 0;if(nums.size() == 1) return nums[0];//2. 遞推公式//當前節點的結果有兩種情況一中是投當前節點，一種是不偷當前節點//偷當前節點就是，前一個節點的最優解：dp[i-1]//不偷當前節點就是前一個節點不能偷，所以是dp[i-2] + nums[i];//所以遞推公式就是 dp[i] = max(dp[i-1], dp[i-2] + nums[i];//3. 初始化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
leetcode題目鏈接
視頻講解
文章講解
將環形數組，根據題目描述可以，分解為兩種數組
// 注意注釋中的情況二情況三，以及把198.打家劫舍的代碼抽離出來了
class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];int result1 = robRange(nums, 0, nums.size() - 2); // 情況二int result2 = robRange(nums, 1, nums.size() - 1); // 情況三return max(result1, result2);}// 198.打家劫舍的邏輯int robRange(vector<int>& nums, int start, int end) {if (end == start) return nums[start];vector<int> dp(nums.size());dp[start] = nums[start];dp[start + 1] = max(nums[start], nums[start + 1]);for (int i = start + 2; i <= end; i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[end];}
};
337.打家劫舍III
leetcode題目鏈接
視頻講解
文章講解
動態規劃結合樹形結構，比較難
class Solution {
public://int dp[2] = {0}; dp[0] 表示不偷當前節點，dp[1] 表示偷當前節點vector<int> robTree(TreeNode * node) {if(node == nullptr) return {0,0};vector<int> left(2,0);vector<int> right(2,0);left = robTree(node->left); //左right = robTree(node->right);//右// 中，后續遍歷，已知左右的值推出當前節點的值//不偷當前節點就是要偷 左節點和有節點， 將左節點偷和不偷的最大值和右節點頭或者不偷的最大值加一起int tmp1 = max(left[0], left[1]) + max(right[0], right[1]);//偷當前節點的話, 就是將當前節點的值加上，左節點和有節點都偷的和int tmp2 = node->val + left[0] + right[0];return {tmp1, tmp2};}int rob(TreeNode* root) {vector<int> vec(2,0);vec = robTree(root);//返回根節點偷或者不偷的最大值return max(vec[0], vec[1]);}
};
)
)
