LeetCode讲解篇之740. 删除并获得点数
题目描述
题解思路
首先对于这题我们如果将所有点数装入一个切片f中，该切片f中的i号下标表示所有点数为i的点数之和
那么这题就转换成了打家劫舍这道题，也就是求选择了切片中某个下标的元素后，该下标相邻元素就不能选择，求最终能选择的元素之和的最大值
那么在切片的[0, i]范围内选择元素的最大值 = max(i号索引元素 + [0, i - 2]范围内选择元素的最大值, [0, i - 1])
题解代码
func deleteAndEarn(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
n := nums[0]
for i := 1; i < len(nums); i ++ {
n = max(n, nums[i])
}
f := make([]int, n + 1)
for i := 0; i < len(nums); i++ {
f[nums[i]] += nums[i]
}
// a: [0, i - 2]范围内的最大值， b: [0, i - 1]范围内的最大值
a, b := f[0], max(f[0], f[1])
for i := 2; i <= n; i++ {
a, b = b, max(b, a + f[i])
}
return b
}
题解链接
https://leetcode.cn/problems/delete-and-earn/description/
原文地址：https://blog.csdn.net/qq_67733273/article/details/142886085
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！