文章目录
- 题目描述
- 题解思路
- 题解代码
- 题目链接
题目描述
题解思路
首先对于这题我们如果将所有点数装入一个切片f中，该切片f中的i号下标表示所有点数为i的点数之和
那么这题就转换成了打家劫舍这道题，也就是求选择了切片中某个下标的元素后，该下标相邻元素就不能选择，求最终能选择的元素之和的最大值
那么在切片的[0, i]范围内选择元素的最大值 = max(i号索引元素 + [0, i - 2]范围内选择元素的最大值, [0, i - 1]范围内选择元素的最大值)
题解代码
impl Solution {pub fn delete_and_earn(nums: Vec<i32>) -> i32 {if nums.len() == 1 {return nums[0];}let mut max_val = nums[0];for &num in &nums {max_val = max_val.max(num);}let mut f = vec![0; max_val as usize + 1];for &num in &nums {f[num as usize] += num;}let (mut a, mut b) = (f[0], f[1].max(f[0]));for i in 2..=max_val as usize {(a, b) = (b, b.max(a + f[i]));}b}
}
题目链接
https://leetcode.cn/problems/delete-and-earn/
