网站会对特殊的ip做跳转,服务公司税率,江西医院网站建设,淮安建设机械网站制作动态规划 - 740. 删除并获得点数(C#和C实现)
题目描述
给你一个整数数组 nums #xff0c;你可以对它进行一些操作。
每次操作中#xff0c;选择任意一个 nums[i] #xff0c;删除它并获得 nums[i] 的点数。之后#xff0c;你必须删除每个等于 nums[i] - 1 或 nums[i] …动态规划 - 740. 删除并获得点数(C#和C实现)
题目描述
给你一个整数数组 nums 你可以对它进行一些操作。
每次操作中选择任意一个 nums[i] 删除它并获得 nums[i] 的点数。之后你必须删除每个等于 nums[i] - 1 或 nums[i] 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1:
输入: nums [3, 4, 2]
输出: 6
解释:
删除 4 来获得 4 个点数因此 3 也被删除。
之后删除 2 来获得 2 个点数。总共获得 6 个点数。示例 2:
输入: nums [2, 2, 3, 3, 3, 4]
输出: 9
解释:
删除 3 来获得 3 个点数接着要删除两个 2 和 4。
之后删除 3 来获得 3 个点数。总共获得 9 个点数。提示:
1 nums.length 2 * 10^42 * 10^4 nums[i] 10^4
解题思路
动态规划
定义状态 设 dp[i] 表示考虑前 i 个元素从 0 到 i-1所能获得的最大点数。状态转移方程 dp[i] max(dp[i-1], dp[i-2] count[i])即考虑第 i 个元素时最大点数等于不考虑第 i 个元素时的最大点数和考虑第 i 个元素时的最大点数之间的较大值其中 count[i] 表示元素 i 的数量乘以 i 的值。初始状态 dp[0] 0dp[1] count[1] * 1。遍历顺序 从小到大遍历计算每个元素的最大点数。
C#代码实现
public int DeleteAndEarn(int[] nums) {if (nums null || nums.Length 0) {return 0;}int maxVal nums.Max();int[] count new int[maxVal 1];foreach (int num in nums) {count[num];}int[] dp new int[maxVal 1];dp[1] count[1] * 1;for (int i 2; i maxVal; i) {dp[i] Math.Max(dp[i - 1], dp[i - 2] count[i] * i);}return dp[maxVal];
}C代码实现
int deleteAndEarn(int* nums, int numsSize) {if (nums NULL || numsSize 0) {return 0;}int maxVal nums[0];for (int i 0; i numsSize; i) {maxVal fmax(maxVal, nums[i]);}int* count (int*)malloc(sizeof(int) * (maxVal 1));memset(count, 0, sizeof(int) * (maxVal 1));for (int i 0; i numsSize; i) {count[nums[i]];}int* dp (int*)malloc(sizeof(int) * (maxVal 1));dp[0] 0;dp[1] count[1] * 1;for (int i 2; i maxVal; i) {dp[i] fmax(dp[i - 1], dp[i - 2] count[i] * i);}int result dp[maxVal];free(count);free(dp);return result;
}时间复杂度和空间复杂度
时间复杂度O(N M)其中 N 是数组的长度M 是数组中的元素值的范围。需要遍历数组并统计每个元素的数量同时需要计算每个元素值的最大点数。空间复杂度O(M)其中 M 是数组中的元素值的范围。使用了一个大小为 M1 的数组来保存每个元素的数量和最大点数。
参与点评
读者朋友们,如果您在阅读过程中,对文章的质量、易理解性有任何建议,欢迎在评论区指出,我会认真改进。
