代码随想录算法训练营第三十六天| 198.打家劫舍 213.打家劫舍II 337.打家劫舍III

Smartisan / 2023-07-24 / 原文

198.打家劫舍

要求：

给定一个nums，要求取得最大值，但是不可以选择两个相邻的数

dp定义：

dp[n]，取到第N个数字的时候，最大值

递推公式：

取：nums[i] + dp[j-2]

不取： nums[i-1];

代码：

 1 // 在两个数字不相邻的情况下，得到的最大金额
 2 // 思路：
 3 // dp[n] 第N个数字时的最大金额数
 4 // 难点：
 5 //  1,如何做到全局最大 4 7 9 1
 6 //  2,中间还可能不相隔 2 1 1 2 
 7 // 
 8 // dp[j] 取，不取
 9 // dp[j-1] , value[i]+dp[j-2];.
10 // 
11 // 初始化？因为第0个也不一定被拿到
12 // 
13 // 根据定义：dp[0] = nums[0] dp[1] = max
14 // 
15 // 如何巧妙的可以用到之前的数值，同时不固定必须的选择顺序，
16 // dp = max(dp[j-1], nums[1]+dp[j-2])
17 //
18 int rob(vector<int>& nums) {
19     if (nums.size() == 1)return nums[0];
20 
21     vector<int>dp(nums.size(), 0);
22     dp[0] = nums[0];
23     dp[1] = max(nums[0], nums[1]);
24 
25     for (int i = 2; i < nums.size(); i++)
26     {
27         dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
28     }
29 
30     return dp[nums.size() - 1];
31 }

213.打家劫舍II

要求：

首尾是相连的，如何在环里面找到最大值？

难点：

.哪个点作为初始化，第0个，不可能直接取，因为和尾部有关联

思路：

分成多步，拆成线性的：

1，取头

2，取尾

代码：

 1 // 要求：这些数字是环形，在不相邻的情况下，得到最大值
 2 // dp[n] 第N个数字时，最大的金钱数
 3 // 难点：
 4 //  1，初始化的时候第0个 如何初始化
 5 // 需要总结，如何破环
 6 // 
 7 // 如何破环：
 8 // 把问题分成多步进行思考：取头，取尾
 9 //
10 int rob(vector<int>& nums) {
11     if (nums.size() == 1) return nums[0];
12     if (nums.size() == 2) return max(nums[0], nums[1]);
13     vector<int> head(nums.begin(), nums.end() - 1);
14     vector<int> tail(nums.begin() + 1, nums.end());
15 
16     int reuslt1 = 0, result2 = 0;
17 
18     vector<int> dp1(head.size(), 0), dp2(tail.size(), 0);
19     dp1[0] = nums[0];
20     dp1[1] = max(nums[0], nums[1]);
21 
22     dp2[0] = nums[1];
23     dp2[1] = max(nums[2], nums[1]);
24 
25     for (int i = 2; i < nums.size(); i++)
26     {
27         if (i != nums.size() - 1)
28         {
29             dp1[i] = max(dp1[i - 1], nums[i] + dp1[i - 2]);
30         }
31 
32         if (i >= 3)
33         {
34             dp2[i-1] = max(dp2[i - 2], nums[i] + dp2[i - 3]);
35         }
36     }
37 
38     return max(dp1[nums.size() - 2], dp2[nums.size() - 2]);
39 }