【刷题笔记】删除并获取最大点数粉刷房子

本文主要是介绍【刷题笔记】删除并获取最大点数粉刷房子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

欢迎来到破晓的历程的博客

⛺️不负时光，不负己✈️

题目一

题目链接：删除并获取最大点数
思路：

预处理
状态表示

在这里插入图片描述

状态转移方程
代码如下：

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}
};

思考：我们是如何将这道题目和打家劫舍问题联系在一起的

这道题目要求必须删除相邻的数据，和打家劫舍问题中的不能偷相邻的两家的东西非常相似。所以我们就可以将本题转化为打家劫舍问题。但是本题的数据不一定是连续的，所以我们需要预处理一步。转化成连续的。

题目二

题目链接：粉刷房子
思路：
在这里插入图片描述

代码如下：

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]);}
};