【算法挨揍日记】day23——740. 删除并获得点数、LCR 091. 粉刷房子

今天药忘吃喽~ 2024-02-20 12:42 69阅读 0赞

## 740. 删除并获得点数 ##

[740. 删除并获得点数][740.]

### 题目描述： ###

给你一个整数数组 `nums` ，你可以对它进行一些操作。

每次操作中，选择任意一个 `nums[i]` ，删除它并获得 `nums[i]` 的点数。之后，你必须删除 **所有** 等于 `nums[i] - 1` 和 `nums[i] + 1` 的元素。

开始你拥有 `0` 个点数。返回你能通过这些操作获得的最大点数。![519171e2a88f40f6a6155f822491739b.png][]

### 解题思路： ###

> 我们先将sort排序一下，然后再用一个额外的数组将nums的元素映射到arr的下标
> 
> 状态表示：
> 
> f\[i\]，g\[i\]表示以i为结尾，i位置选和i位置不选的最大点数
> 
> 状态转移方程：
> 
> f\[i\]=g\[i-1\]+nums\[i\]
> 
> g\[i\]=max(f\[i-1\],g\[i-1\])
> 
> 初始化：
> 
> f\[0\]=nums\[0\],g\[0\]=0
> 
> 填表顺序：左到右
> 
> 返回值：max(f\[n-1\],g\[n-1\])

### 解题代码： ###

class Solution {
    public:
        int deleteAndEarn(vector<int>& nums) {
            sort(nums.begin(),nums.end());
            int n=nums.size();
            int len=nums[n-1]+1;
            vector<int>arr(len,0);
            for(int i=0;i<n;i++)
            {
                int x=nums[i];
                arr[x]+=x;
            }
            vector<int>f(len,0);
            vector<int>g(len,0);
            f[0]=arr[0];
            for(int i=1;i<len;i++)
            {
                f[i]=g[i-1]+arr[i];
                g[i]=max(f[i-1],g[i-1]);
            }
            return max(f[len-1],g[len-1]);
        }
    };

--------------------

## LCR 091. 粉刷房子 ##

[LCR 091. 粉刷房子][LCR 091.]

### 题目描述： ###

假如有一排房子，共 `n` 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 `n x 3`的正整数矩阵 `costs` 来表示的。

例如，`costs[0][0]` 表示第 0 号房子粉刷成红色的成本花费；`costs[1][2]` 表示第 1 号房子粉刷成绿色的花费，以此类推。

请计算出粉刷完所有房子最少的花费成本。

![cebb347c8ce34df6bbc9fb650f0e3dec.png][]

### 解题思路： ###

> 状态表示：
> 
> f\[i\]表示以i位置为结尾，选择红色（第一个）的最小金额
> 
> g\[i\]表示以i位置为结尾，选择蓝色（第二个）的最小金额
> 
> v\[i\]表示以i位置为结尾，选择绿色（第3个）的最小金额
> 
> 状态转移方程：
> 
> f\[i\]=min(g\[i-1\],v\[i-1\])+costs\[i\]\[0\];
> 
> g\[i\]=min(f\[i-1\],v\[i-1\])+costs\[i\]\[1\];
> 
> v\[i\]=min(f\[i-1\],g\[i-1\])+costs\[i\]\[2\];
> 
> 初始化:
> 
> f\[0\]=costs\[0\]\[0\];
> 
> g\[0\]=costs\[0\]\[1\];
> 
> v\[0\]=costs\[0\]\[2\];
> 
> 填表顺序：左到右
> 
> 返回值：min(min(f\[n-1\],g\[n-1\]),v\[n-1\]);

### 解题代码： ###

class Solution {
    public:
        int minCost(vector<vector<int>>& costs) {
            int n=costs.size();
            vector<int>f(n,0);
            vector<int>g(n,0);
            vector<int>v(n,0);
            f[0]=costs[0][0];
            g[0]=costs[0][1];
            v[0]=costs[0][2];
            for(int i=1;i<n;i++)
            {
                f[i]=min(g[i-1],v[i-1])+costs[i][0];
                g[i]=min(f[i-1],v[i-1])+costs[i][1];
                v[i]=min(f[i-1],g[i-1])+costs[i][2];
            }
            return min(min(f[n-1],g[n-1]),v[n-1]);
        }
    };

[740.]: https://leetcode.cn/problems/delete-and-earn/
[519171e2a88f40f6a6155f822491739b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/467eb939780440bda7c47fb6784c3533.png
[LCR 091.]: https://leetcode.cn/problems/JEj789/
[cebb347c8ce34df6bbc9fb650f0e3dec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/af28218586b94aa9b396052e2998b3be.png