题目一
题目链接：删除并获取最大点数 思路：
- 预处理
- 状态表示
在这里插入图片描述- 状态转移方程
代码如下：
代码语言：javascript复制class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
int N=10001;
int arry[N]={0};
for(auto x:nums)
{
arry[x] =x;
}
//接下来，就是打家劫舍问题
vector<int> f(N);
vector<int> g(N);
f[0]=arry[0];
g[0]=0;
for(int i=0;i<N;i )
{
f[i]=g[i-1] arry[i];
g[i]=max(g[i-1],f[i-1]);
}
return max(f[10000],g[10000]);
English
}
};思考：我们是如何将这道题目和打家劫舍问题联系在一起的
这道题目要求必须删除相邻的数据，和打家劫舍问题中的不能偷相邻的两家的东西非常相似。所以我们就可以将本题转化为打家劫舍问题。但是本题的数据不一定是连续的，所以我们需要预处理一步。转化成连续的。
题目二
题目链接：粉刷房子 思路：
在这里插入图片描述
在这里插入图片描述代码如下：
代码语言：javascript复制class Solution {
public:
int minCost(vector<vector<int>>& costs) {
int m=costs.size();
if(m==1) return min(costs[0][1],costs[0][0],costs[0][2]);
vector<vector<int>>dp(m 1,vector<int>(3));
for(int i=1;i<m 1;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[m][0],dp[m][1],dp[m][2]);
}
};
