动态规划入门题目| MarsCode

196 小M的得分挑战

问题描述

小M有一个长度为 n 的数组 a，初始分数为 0。

小M每次可以选择两个整数，并且这两个数的差值不能超过 k。小M会获得这两个数的乘积作为分数，并且已经被选择过的数不能再被选择。

你需要帮助小M计算，最多能获得多少分数？

测试样例

样例1：

输入：n = 6, k = 2, a = [1, 1, 4, 5, 1, 4]
输出：21

样例2：

输入：n = 4, k = 1, a = [3, 3, 4, 4]
输出：25

样例3：

输入：n = 5, k = 0, a = [2, 2, 2, 2, 2]
输出：8

思路解析

  1. 排序数组： 为了方便配对，我们首先将数组 a 按升序排序。这有助于我们更容易地找到符合条件的配对。

  2. 定义DP数组： 定义一个 DP 数组 dp，其中 dp[i] 表示前 i 个元素能够获得的最大分数。

  3. 状态转移： 对于每一个位置 i，有两种选择：

    • 不配对第 i 个元素：则 dp[i] = dp[i-1]。
    • 配对第 i 个元素与第 i-1 个元素（如果它们的差值不超过 k）：则 dp[i] = dp[i-2] + a[i-1] * a[i-2]。

    我们取这两种选择中的最大值作为 dp[i] 的值。

  4. 边界条件：

    • dp[0] = 0：没有元素时，分数为0。
    • dp[1] = 0：只有一个元素时，无法配对，分数为0。

  5. 最终结果： 最终的最大分数为 dp[n]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(n: int, k: int, a: list) -> int:
    # 将数组按升序排序
    a_sorted = sorted(a)
    
    # 初始化DP数组，长度为n+1
    dp = [0] * (n + 1)
    
    for i in range(2, n + 1):
        # 不配对当前元素
        dp[i] = dp[i - 1]
        
        # 尝试配对当前元素与前一个元素
        if a_sorted[i - 1] - a_sorted[i - 2] <= k:
            dp[i] = max(dp[i], dp[i - 2] + a_sorted[i - 1] * a_sorted[i - 2])
    
    return dp[n]