医院建设网站要求分析 amp,聪明的上海网站,怀远建设局门户网站,wordpress zh_cn.po740. 删除并获得点数 740. 删除并获得点数
题目描述#xff1a;
给你一个整数数组 nums #xff0c;你可以对它进行一些操作。
每次操作中#xff0c;选择任意一个 nums[i] #xff0c;删除它并获得 nums[i] 的点数。之后#xff0c;你必须删除 所有 等于 nums[i] - 1…740. 删除并获得点数 740. 删除并获得点数
题目描述
给你一个整数数组 nums 你可以对它进行一些操作。
每次操作中选择任意一个 nums[i] 删除它并获得 nums[i] 的点数。之后你必须删除 所有 等于 nums[i] - 1 和 nums[i] 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。 解题思路 我们先将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(vectorint nums) {sort(nums.begin(),nums.end());int nnums.size();int lennums[n-1]1;vectorintarr(len,0);for(int i0;in;i){int xnums[i];arr[x]x;}vectorintf(len,0);vectorintg(len,0);f[0]arr[0];for(int i1;ilen;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. 粉刷房子
题目描述
假如有一排房子共 n 个每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然因为市场上不同颜色油漆的价格不同所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
例如costs[0][0] 表示第 0 号房子粉刷成红色的成本花费costs[1][2] 表示第 1 号房子粉刷成绿色的花费以此类推。
请计算出粉刷完所有房子最少的花费成本。 解题思路 状态表示 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(vectorvectorint costs) {int ncosts.size();vectorintf(n,0);vectorintg(n,0);vectorintv(n,0);f[0]costs[0][0];g[0]costs[0][1];v[0]costs[0][2];for(int i1;in;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]);}
};
