簡單多狀態(tài)問題
文章目錄
- 一.按摩師
- 二.打家劫舍系列
- 三.刪除并獲得點數(shù)
- 四.粉刷房子
1.按摩師
力扣鏈接：力扣
一個有名的按摩師會收到源源不斷的預(yù)約請求，每個預(yù)約都可以選擇接或不接。在每次預(yù)約服務(wù)之間要有休息時間，因此她不能接受相鄰的預(yù)約。給定一個預(yù)約請求序列，替按摩師找到最優(yōu)的預(yù)約集合（總預(yù)約時間最長），返回總的分鐘數(shù)。
首先我們分析一下題目：1.每個預(yù)約可以選擇接或者不接 2.不能接受相鄰的預(yù)約。
1.狀態(tài)表示
我們用dp[i]表示i位置的最長分鐘數(shù)，而i位置又可以分為兩種情況，一種是接，一種是不接，所以我們用兩個dp表來表示狀態(tài)。
f[i]表示接i位置的最長分鐘數(shù)
g[i]表示不接i位置的最長分鐘數(shù)?
2.狀態(tài)轉(zhuǎn)移方程
因為f[i]表示接i位置的預(yù)約，由于題目要求不能接受相鄰的預(yù)約，所以我們一定不能接受i-1位置的預(yù)約，而g[i-1]就表示不接i-1位置的最長分鐘數(shù)，又因為我們接了i位置要加上i位置的分鐘數(shù)，所以
f[i] = g[i-1] + nums[i];
g[i]表示不接i位置，那么我們可以選擇接受i-1位置或者不接受i-1位置，又因為我們要的是最大值，所以取這兩種情況的較大值即可。
g[i] = max(f[i-1],g[i-1]）
3.初始化
從狀態(tài)轉(zhuǎn)移方程來看，我們造成越界的位置只有f[0]和g[0]，而f[0]表示接受0位置的最長分鐘數(shù)，那么f[0] = nums[0]? ? ?g[0] = 0.
4.填表
已知f[0]和g[0]所以從左向右依次填表，兩個表一起填
5.返回值
因為預(yù)約時長都是正數(shù)，所以越到后面時間越長，那么最長的只有兩種情況：最后一個位置接或者最后一個位置不接，此題要求最大值，所以是這兩個情況的較大值。
class Solution {
public:
int massage(vector<int>& nums) {
if (nums.size()==0) return 0;
//創(chuàng)建dp表
int n = nums.size();
vector<int> f(n,0),g(n,0);
f[0] = nums[0],g[0] = 0;
for (int i = 1;i<n;i++)
{
f[i] = g[i-1] + nums[i];
g[i] = max(f[i-1],g[i-1]);
}
return max(f[n-1],g[n-1]);
}
};?注意：此題會有nums.size()為0的情況，所以需要單獨判斷。
2.打家劫舍系列
1.打家劫舍I
力扣鏈接：力扣
你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。
給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組，計算你?不觸動警報裝置的情況下?，一夜之內(nèi)能夠偷竊到的最高金額。
?1.狀態(tài)表示
由于每個位置存在偷與不偷兩個狀態(tài)，所以需要兩個表來表示。
f[i]表示偷i位置的最高金額
g[i]表示不偷i位置的最高金額
2.狀態(tài)轉(zhuǎn)移方程
f[i] = g[i-1] + nums[i];
g[i] = max(f[i-1],g[i-1])
3.初始化，4.填表，5.返回值
與第一題同理。
對于這個題我們應(yīng)該很熟悉吧，沒錯！和第一題按摩師簡直一模一樣，我們直接把按摩師的代碼復(fù)制過來：
?相同的代碼，立馬就搞定了，我們將這道題拿出來是為了引出打家劫舍II和III，所以并不是沒有用哦~
2.打家劫舍II
力扣鏈接：力扣
你是一個專業(yè)的小偷，計劃偷竊沿街的房屋，每間房內(nèi)都藏有一定的現(xiàn)金。這個地方所有的房屋都?圍成一圈?，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警?。
給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組，計算你?在不觸動警報裝置的情況下?，今晚能夠偷竊到的最高金額。
注意：和I不同的是，這道題的前后是一個圈，也就是說這是一個環(huán)形問題，下面我們來解決這道題。
首先我們能將問題分為兩種情況，第一種是偷第一家的情況，第二種是不偷第一家的情況。
如果偷第一家，那么第二家和最后一家不能偷，也就是說我們只需要對2到n-2這個范圍做一次打家劫舍I，最后加上nums【0】即可。
如果不偷第一家，那么1到n-1這個范圍內(nèi)可以隨便偷，所以對1到n-1這個范圍內(nèi)做一次打家劫舍I即可。
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
return max(nums[0]+rob1(nums,2,n-2),rob1(nums,1,n-1));
}
int rob1(vector<int>& nums,int left,int right)
{
if (left>right) return 0;
int n = nums.size();
vector<int> f(n, 0), g(n, 0);
f[left] = nums[left], g[left] = 0;
for (int i = left+1; i <= right; i++)
{
f[i] = g[i - 1] + nums[i];
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[right], g[right]);
}
};?注意：當我們left大于right的時候那么一定是越界的情況，這種情況返回0即可。當我們將區(qū)間定為left到right這個閉區(qū)間，那么就從left+1開始填表，填到right，最后返回的時候也是返回dp表中right的位置，這里一定要畫圖映射位置關(guān)系。
3.刪除并獲得點數(shù)
力扣鏈接：力扣
給你一個整數(shù)數(shù)組?nums?，你可以對它進行一些操作。
每次操作中，選擇任意一個?nums[i]?，刪除它并獲得?nums[i]?的點數(shù)。之后，你必須刪除?所有?等于?nums[i] - 1?和?nums[i] + 1?的元素。
開始你擁有?0?個點數(shù)。返回你能通過這些操作獲得的最大點數(shù)。
?首先通過題目我們可以看到當我們刪除X獲取X的點數(shù)后，必須刪除X-1和X+1的元素，我們發(fā)現(xiàn)這與打家劫舍的問題非常像，都是不能獲得相鄰元素的值，那么我們該如何將這個問題轉(zhuǎn)化為打家劫舍問題呢？其實很簡單，因為X-1?和 X 和 X+1這三個數(shù)都是相鄰的，我們直接將nums映射到一個與下標同值的表中，比如3就放在下標為3的位置，并且給這個位置加上3，然后我們對這個新數(shù)組做一次打家劫舍就得到了最大點數(shù)。
比如實例2，映射后變成如下圖：
然后我們對這個數(shù)組做一次打家劫舍，獲取的最大點數(shù)就是9.
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
int hash[10001] = {0};
const int n = 10001;
for (auto& a:nums)
{
hash[a]+=a;
}
vector<int> f(n, 0), g(n, 0);
for (int i = 1; i < n; i++)
{
f[i] = g[i - 1] + hash[i];
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[n-1], g[n-1]);
}
};?此方法就是用空間換時間。
4.粉刷房子
力扣鏈接：力扣
假如有一排房子，共?n?個，每個房子可以被粉刷成紅色、藍色或者綠色這三種顏色中的一種，你需要粉刷所有的房子并且使其相鄰的兩個房子顏色不能相同。
當然，因為市場上不同顏色油漆的價格不同，所以房子粉刷成不同顏色的花費成本也是不同的。每個房子粉刷成不同顏色的花費是以一個?n x 3?的正整數(shù)矩陣?costs?來表示的。
例如，costs[0][0]?表示第 0 號房子粉刷成紅色的成本花費；costs[1][2]?表示第 1 號房子粉刷成綠色的花費，以此類推。
請計算出粉刷完所有房子最少的花費成本。
?首先我們通過題目可以知道限制條件為：相鄰房屋不能涂成同一個顏色，下面我們開始解題。
1.狀態(tài)表示
dp【i】表示第i個房子所花費的最低成本，由于每個房子都可以涂成三種顏色，所以dp[i]又可以劃分成3個狀態(tài)。
dp[i][0]表示第i個房子涂成紅色的最低成本
dp[i][1]表示第i個房子涂成藍色的最低成本
dp[i][2]表示第i個房子涂成綠色的最低成本
2.狀態(tài)轉(zhuǎn)移方程
dp[i][0] = min(dp[i-1][1],dp[i-1][2]) + costs[i][0];
dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + costs[i][1];
dp[i][2] = min(dp[i-1][0],dp[i-1][1]) + costs[i][2];
由于每個房子不能涂成相同顏色，所以第i層的房子如果是紅色，那么第i-1層就只能是藍色和綠色。
3.初始化
由于第一個房子不受前面任何房子的影響（i-1越界），所以第一個房子的三個狀態(tài)都是已知的
dp[0][0] = costs[0][0],
dp[0][1] = costs[0][1],
dp[0][2] = costs[0][2];
4.填表
從左向右依次填表，三個表一起填
5.返回值
返回最后一個房子的三種狀態(tài)的最小值。
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
int n = costs.size();
vector<vector<int>> dp(n,vector<int>(3));
dp[0][0] = costs[0][0],dp[0][1] = costs[0][1],dp[0][2] = costs[0][2];
for (int i = 1;i<n;i++)
{
dp[i][0] = min(dp[i-1][1],dp[i-1][2]) + costs[i][0];
dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + costs[i][1];
dp[i][2] = min(dp[i-1][0],dp[i-1][1]) + costs[i][2];
}
int ret = dp[n-1][0];
for (int i =1;i<3;i++)
{
if (dp[n-1][i]<ret)
{
ret = dp[n-1][i];
}
}
return ret;
}
};當然我們也可以將最后取最小值的代碼簡化一下：文章來源：http://www.zghlxwxcb.cn/news/detail-480776.html
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
int n = costs.size();
vector<vector<int>> dp(n,vector<int>(3));
dp[0][0] = costs[0][0],dp[0][1] = costs[0][1],dp[0][2] = costs[0][2];
for (int i = 1;i<n;i++)
{
dp[i][0] = min(dp[i-1][1],dp[i-1][2]) + costs[i][0];
dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + costs[i][1];
dp[i][2] = min(dp[i-1][0],dp[i-1][1]) + costs[i][2];
}
int ret = min(dp[n-1][0],min(dp[n-1][1],dp[n-1][2]));
return ret;
}
};以上就是本篇文章的5道動態(tài)規(guī)劃習(xí)題，還是建議大家在做動態(tài)規(guī)劃習(xí)題的時候要多畫圖。文章來源地址http://www.zghlxwxcb.cn/news/detail-480776.html
到了這里，關(guān)于60題學(xué)會動態(tài)規(guī)劃系列：動態(tài)規(guī)劃算法第三講的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
