[dp5_多狀態dp] 按摩師 | 打家劫舍 II | 刪除并獲得點數

1.面試題 17.16. 按摩師

題解

2.打家劫舍 II

題解

3.刪除并獲得點數

題解

4.粉刷房子

題解

一定要有這樣的能力，碰到一個新題的時候，可以往之前做過的題方向靠！

打家劫舍問題模型: ?不能選擇相鄰的兩個數，并且要最終選擇的數最大。
解決辦法: ?維護多個DP表，return 最值

后面的三個問題，其實都可以理解為是第一個題目的變形，例如說
對環形進行分情況，變為鏈形，抽離出DP 函數，使用兩次
進行一個預處理，再 DP
兩種情況變為多種情況

但是其實解決的思路都是一樣的

1.面試題 17.16. 按摩師

鏈接： 面試題 17.16. 按摩師

一個有名的按摩師會收到源源不斷的預約請求，每個預約都可以選擇接或不接。在每次預約服務之間要有休息時間，因此她不能接受相鄰的預約。給定一個預約請求序列，替按摩師找到最優的預約集合（總預約時間最長），返回總的分鐘數。

注意：本題相對原題稍作改動

示例 1：

輸入： [1,2,3,1]
輸出： 4
解釋： 選擇 1 號預約和 3 號預約，總時長 = 1 + 3 = 4。

題解

圓圈表示預約，每個預約可以接或不接
不能接受相鄰的預約

最優的預約集合（總預約時間最長），返回總的分鐘數。

1.狀態表示

經驗 + 題目要求

dp[i] 表示：選擇到 i 位置的時候，此時最長預約時長。

但是 i 位置可以選或者不選，因此繼續細化

f[i] 表示：選擇到 i 位置的時候，nums[i] 必選，此時最長預約時長
g[i] 表示：選擇到 i 位置的時候，nums[i] 不選，此時最長預約時長

因為這個位置的設置，是和上一個位置有關的

2.狀態轉移方程

依據題目所給的相鄰不能選規則
f[i]=g[i-1]+nums[i] //選 i
g[i]=max(f[i-1],g[i-1]) //不選 i

選的話別忘記 i 位置的預約時長，然后相信計算機就好啦

注釋：

g[i] 表示不選 i 位置，此時最長預約時長。 i 位置不選，那 i - 1 位置可選可不選，我們要找的是 0 ~ i - 1區間最長預約時長，有兩種情況

選 i - 1 位置，而 f[i - 1] 表示必選 i - 1 位置此時最長預約時長，
不選 i - 1 位置，g[i - 1] 表示不選 i - 1 位置此時最長預約時長

3.初始化

填表時不越界

這里我們也可以添加虛擬節點，但是這道題初始化太簡單了，因此就不要添加虛擬節點。

填f[0]，g[0] 會越界，而f[0]表示必選0位置，g[0]表示不選0位置，因此

f[0] = nums[0] ，g[0] = 0

4.填表

從左往右兩個表一起填~

5.返回值

返回到達最后一個位置時最長預約時長
max( f[n - 1]，g[n - 1] )

class Solution {
public:int massage(vector<int>& nums) {//多狀態dp//f  gint n=nums.size();if(n==0) return 0;if(n==1) return nums[0];//注意 邊界處理vector<int> f(n,0);vector<int> g(n,0);f[0]=nums[0];//選for(int i=1;i<n;i++){f[i]=g[i-1]+nums[i];g[i]=max(g[i-1],f[i-1]);}return max(f[n-1],g[n-1]);       }
};

if(n==0) return 0;

if(n==1) return nums[0];

//注意邊界處理

2.打家劫舍 II

打家劫舍：環形變種

鏈接： 213. 打家劫舍 II

你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金。這個地方所有的房屋都 圍成一圈 ，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警 。

給定一個代表每個房屋存放金額的非負整數數組，計算你 在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額。

示例 1：

輸入：nums = [2,3,2]
輸出：3
解釋：你不能先偷竊 1 號房屋（金額 = 2），然后偷竊 3 號房屋（金額 = 2）, 因為他們是相鄰的。

題解

這道題相比于打家劫舍I 多了這個條件：這個地方所有的房屋都圍成一圈
這意味著第一個房屋和最后一個房屋是緊挨著的，也就是說現在成了一個環路了。

同時，相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

?分類討論：

根據一個位置選or不選可以把問題從環形問題轉化為線性問題

好好畫下圖，就可以想通啦

int rob(vector<int>& nums) {int n = nums.size();//分類討論兩種情況下最大值return max(dp(nums, 2, n-2) + nums[0], dp(nums, 1, n - 1));}

接下來是打家劫舍I的分析，和上面那道題幾乎一模一樣

1.狀態表示

經驗 + 題目要求

f[i] 表示：偷到 i 位置的時候，偷 nums[i] ，此時的最大金額
g[i] 表示：偷到 i 位置的時候，不偷 nums[i] ，此時的最大金額

2.狀態轉移方程

f[i] = g[i-1] +nums[ i]
g[i] =max( f[i-1],g[i-1])

3.初始化

填表時不越界
f[0] = nums[0] ，g[0] = 0

4.填表

從左往右兩個表一起填

5.返回值

返回偷到最后一個位置時最大金額
max( f[n - 1]，g[n - 1] )

class Solution {
public:int n;int rob(vector<int>& nums) {n=nums.size();if(n==0) return 0;if(n==1) return nums[0];if(n==2) return nums[0]>nums[1]?nums[0]:nums[1];return max(dp(nums,1,n-1),dp(nums,2,n-2)+nums[0]);//如何 實現 對環的處理的呢？
//通過 對第一個位置的 選 不選
//將dp 隔離為一個函數，兩次調用~}int dp(vector<int>& nums,int begin,int end){vector<int> f(n,0);vector<int> g(n,0);f[begin]=nums[begin];for(int i=begin+1;i<=end;i++){f[i]=g[i-1]+nums[i];g[i]=max(g[i-1],f[i-1]);}return max(f[end],g[end]);} 
};

return max(dp(nums,1),dp(nums,2)+nums[0]);

如何實現對環的處理的呢？
通過對第一個位置的選不選
將dp 隔離為一個函數，兩次調用~

3.刪除并獲得點數

打家劫舍：要預處理版

鏈接： 740. 刪除并獲得點數

每次操作中，選擇任意一個 nums[i] ，刪除它并獲得 nums[i] 的點數。之后，你必須刪除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。

開始你擁有 0 個點數。返回你能通過這些操作獲得的最大點數。

示例 1：

輸入：nums = [3,4,2]
輸出：6
解釋：
刪除 4 獲得 4 個點數，因此 3 也被刪除。
之后，刪除 2 獲得 2 個點數。總共獲得 6 個點數。

示例 2：

輸入：nums = [2,2,3,3,3,4]
輸出：9
解釋：
刪除 3 獲得 3 個點數，接著要刪除兩個 2 和 4 。
之后，再次刪除 3 獲得 3 個點數，再次刪除 3 獲得 3 個點數。
總共獲得 9 個點數。

題解

給你一個整數數組 nums ，你可以對它進行一些操作。

每次操作中，選擇任意一個 nums[i] ，刪除它并獲得 nums[i] 的點數。
之后，你必須刪除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。
開始你擁有 0 個點數。返回你能通過這些操作獲得的最大點數。

對于刪除它并獲得 nums[i] 的點數。

之后，你必須刪除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。
刪除所有等于 nums[i] - 1 和 nums[i] + 1 的元素也就是說值等于這兩個的數不能選了。
因此我們可以先對數組排一下序，方便找到 nums[i] - 1 和 nums[i] + 1 的元素。

一定要有這樣的能力，碰到一個新題的時候，可以往之前做過的題方向靠！

比如這道題如果是有序的并且中間數沒有少，就像打家劫舍的問題。
比如說1、2、3、4、5。
選 1 之后不能選 2 了，是不是就是不能選擇相鄰的兩個數，并且要最終選擇的數最大。

所以如果說，數組是有序的話并且中間沒有間隔，就是 “打家劫舍” 問題。

但是這里的數并不是那么連續的。如果中間數斷了，就不是 “打家劫舍” 問題。
比如這里選 2 之后，還能選 4.

所以我們可以先用數組arr，把這些數先統計一下。

下標 i 表示這個數是幾，arr[i] 表示 " i " 這個數出現的總和。
為什么預處理到數組中，因為下標 i 是有序的。
然后就可以不要nums了，相當于在arr數組做一次 “打家劫舍” 。

比如說選了下標1里面的數，那下標 2 里面的數就不能要了，也就相當于選擇當前這個數，相鄰的數不能選了。可以選后面其他的數。

預處理：將數組中的數，統計到 arr 中，然后在 arr 中，做一次 “打家劫舍” 問題即可

1.狀態表示

經驗 + 題目要求
f[i] 表示：選到 i 位置的時候， nums[i] 必選，此時能獲得的最大點數
g[i] 表示：偷到 i 位置的時候，nums[i] 不選，此時能獲得的最大點數

2.狀態轉移方程

f[i]=g[i-1]+arr[i]
g[i]=max(f[i-1], g[i-1])

3.初始化

填表時不越界
f[0] = arr[0] ，g[0] = 0

4.填表

從左往右
兩個表一起填

5.返回值

返回偷到最后一個位置時最大金額
max( f[n - 1]，g[n - 1] )

class Solution {
public:int deleteAndEarn(vector<int>& nums) {sort(nums.begin(),nums.end());int n=nums.size();if(n==0) return 0;if(n==1) return nums[0];vector<int> arr(10001,0);
//預處理 建立映射for (auto num : nums) {arr[num] += num;}//dp 無需管空值，還是和以前一樣就行~int m=arr.size();vector<int> f(m,0);vector<int> g(m,0);f[0]=arr[0];for(int i=1;i<m;i++){f[i]=g[i-1]+arr[i];g[i]=max(g[i-1],f[i-1]);}return max(f[m-1],g[m-1]);}
};

dp 無需管 arr 空值，還是和以前一樣就行~

int m=arr.size();
vector<int> f(m,0);

4.粉刷房子

打家劫舍：選擇兩種變三種

鏈接： LCR 091. 粉刷房子

假如有一排房子，共 n 個，每個房子可以被粉刷成紅色、藍色或者綠色這三種顏色中的一種，你需要粉刷所有的房子并且使其相鄰的兩個房子顏色不能相同。

當然，因為市場上不同顏色油漆的價格不同，所以房子粉刷成不同顏色的花費成本也是不同的。每個房子粉刷成不同顏色的花費是以一個 n x 3 的正整數矩陣 costs 來表示的。

例如，costs[0][0] 表示第 0 號房子粉刷成紅色的成本花費；costs[1][2] 表示第 1 號房子粉刷成綠色的花費，以此類推。

請計算出粉刷完所有房子最少的花費成本。

示例 1：

輸入: costs = [[17,2,17],[16,16,5],[14,3,19]]
輸出: 10
解釋: 將 0 號房子粉刷成藍色，1 號房子粉刷成綠色，2 號房子粉刷成藍色。最少花費: 2 + 5 + 3 = 10。

題解

有n個房子，每個房子都可以被粉刷成紅色，藍色，綠色，相鄰的房子顏色不能相同。
每個房子粉刷成不同顏色的價格由一個3*n的矩陣給出，左邊0 ~ 2表示房子，上面0 ~ 2表示每個房子被粉刷不能顏色的價格。

要找到粉刷完所有房子最少的價格。

這不是剛好符合我們打家劫舍的兩個模型特征了嗎~

1.狀態表示

經驗 + 題目要求

以 i 位置為結尾，當涂到 i 位置的時候此時的最小花費，但是涂到 i 位置還可以細分，涂成紅色，藍色，綠色。

dp[i][0] 表示：粉刷到 i 位置的時候，最后一個位置粉刷上紅色，此時的最小花費
dp[i][1] 表示：粉刷到 i 位置的時候，最后一個位置粉刷上藍色，此時的最小花費
dp[i][2] 表示：粉刷到 i 位置的時候，最后一個位置粉刷上綠色，此時的最小花費

對比打家劫舍的兩種選不選，這里是有三種選擇的可能

也可以這么理解

f[i] == dp[i][0]
g[i] == dp[i][1]

所以有四種五種可能，我們也是這么處理

2.狀態轉移方程

此時分三種情況討論：

如果 i 位置涂成紅色這個位置花費已經固定了 cost[i][0]，我要的是最小花費，只要保證 0 ~ i -1 區間花費最小就行了。
涂到 i - 1 位置只能涂成藍色、綠色，dp[i-1][1]表示涂到 i - 1 位置涂藍色此時最小花費，dp[i-1][2]表示涂到 i - 1 位置涂綠色此時最小花費
因此 i 位置涂成紅色狀態轉移方程就處理了，剩下也是這樣的處理：

3.初始化

填表時不越界

這里我們可以多申請一個空間。這樣就可以把初始化放到填表里面了。但是要注意兩點：

虛擬節點里面的值，要保證后序填表時正確的
下標的映射關系

首先看虛擬節點里面的值應該填多少

可以先考慮沒有虛擬節點第一個位置應該填多少，是不是填的是自己本身啊，因此虛擬節點里面的值我們給0。
因為我們多開一個空間，相當于整體向右移一位，如果要回去矩陣下標應該減 1。

4.填表

從左往右三個表一起填

5.返回值

返回涂到最后一個位置，涂成紅，藍，綠最小花費
多狀態，就每個狀態都維護一個DP表min（dp[n][0]，dp[n][1]，dp[n][2]）

class Solution {
public:int minCost(vector<vector<int>>& costs) {int n=costs.size();vector<vector<int>> dp(n+1,vector<int>(3,0));for(int i=1;i<=n;i++){dp[i][0]=min(dp[i-1][1],dp[i-1][2])+costs[i-1][0];dp[i][1]=min(dp[i-1][0],dp[i-1][2])+costs[i-1][1];dp[i][2]=min(dp[i-1][0],dp[i-1][1])+costs[i-1][2];//注意 下表映射}return min(dp[n][0],min(dp[n][1],dp[n][2]));//對填完了的表 ，進行選擇}
};