本專欄內(nèi)容為：算法學(xué)習(xí)專欄，分為優(yōu)選算法專欄，貪心算法專欄，動(dòng)態(tài)規(guī)劃專欄以及遞歸，搜索與回溯算法專欄四部分。 通過本專欄的深入學(xué)習(xí)，你可以了解并掌握算法。
??博主csdn個(gè)人主頁：小小unicorn
?專欄分類：動(dòng)態(tài)規(guī)劃專欄
??代碼倉庫：小小unicorn的代碼倉庫??
??????關(guān)注我?guī)銓W(xué)習(xí)編程知識(shí)
題目來源
本題來源為：
Leetcode 740. 刪除并獲得點(diǎn)數(shù)
題目描述
給你一個(gè)整數(shù)數(shù)組 nums ，你可以對(duì)它進(jìn)行一些操作。
每次操作中，選擇任意一個(gè) nums[i] ，刪除它并獲得 nums[i] 的點(diǎn)數(shù)。之后，你必須刪除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
開始你擁有 0 個(gè)點(diǎn)數(shù)。返回你能通過這些操作獲得的最大點(diǎn)數(shù)。
題目解析
還是老樣子，先做一下預(yù)處理：
我們將數(shù)組中的數(shù)保存在arr中，轉(zhuǎn)化成一次“打家劫舍”問題
算法原理
1.狀態(tài)表示
經(jīng)驗(yàn)+題目要求
對(duì)于本題而言就是：
f[i]表示：選擇到i位置時(shí)，nums[i]必選，此時(shí)能獲得最大點(diǎn)數(shù)
g[i]表示：選擇到i位置時(shí)，不選nums[i]，此時(shí)能獲得最大點(diǎn)數(shù)
2.狀態(tài)轉(zhuǎn)移方程
和之前一樣：
在i位置選和不選兩種情況
因此狀態(tài)方程為：
f[i]=g[i-1]+nums[i];
g[i]=max(f[i-1],g[i-1]);
3.初始化
只有0位置會(huì)發(fā)生越界，初始化一下0位置即可
4.填表順序
從左往右，兩個(gè)表同時(shí)填
5.返回值
max(f[n-1],g[n-1])
代碼實(shí)現(xiàn)
動(dòng)態(tài)規(guī)劃的代碼基本就是固定的四步：文章來源：http://www.zghlxwxcb.cn/news/detail-842424.html
1.創(chuàng)建dp表
2.初始化
3.填表
4.返回值
本題完整代碼實(shí)現(xiàn)：文章來源地址http://www.zghlxwxcb.cn/news/detail-842424.html
class Solution
{
public:
int deleteAndEarn(vector<int>& nums)
{
const int N =10001;
//預(yù)處理:
int arr[N]={0};
for(auto x:nums)
arr[x]+=x;
//創(chuàng)建dp表
vector<int> f(N);
vector<int> g(N);
//初始化
f[0]=arr[0];
//填表
for(int i=1;i<N;i++)
{
f[i]=g[i-1]+arr[i];
g[i]=max(f[i-1],g[i-1]);
}
//返回值
return max(f[N-1],g[N-1]);
}
};
到了這里，關(guān)于【動(dòng)態(tài)規(guī)劃專欄】專題三：簡單多狀態(tài)dp--------3.刪除并獲得點(diǎn)數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
