python算法问题求解

Question

如下这段代码是蓝桥杯对局匹配问题一个同学给出的答案 我研读了很久 也始终有一点想不明白

为了方便各位老哥解答 n指的是用户总人数 k指的是积分差恰好为k的两个玩家方可匹配 list1是这n个玩家的对应积分值

import os
import sys
n, k = map(int, input().split())
list1 = list(map(int, input().split()))
maxn = max(list1)
if k == 0:
    print(len(set(list1)))
else:
    val = [0 for i in range(maxn + 1)]
    dp = [0 for i in range(maxn + 1)]
    for i in list1:
        val[i] += 1
    res = 0
    for j in range(maxn + 1):
        if 2 * k <= j:
            dp[j] = max(dp[j - k], dp[j - 2 * k] + val[j])
        elif j < k:
            dp[j] = val[j]
        else:
            dp[j] = max(dp[j - k], val[j])
s=0
for i in range(maxn-k+1,maxn+1):
  s+=dp[i]
print(s)

我的疑问就是针对下面那段代码中 dp背包的索引j的实际含义是什么 这个动态规划到底是如何实现的 谢谢各位耐心解答

Answer 1

dp 数组的索引 j 的实际含义是：当前考虑的积分是 j。dp[j] 的值是：在积分为 j 的情况下，最多有多少个用户无法匹配。这个值是根据以下规则计算的：

如果 j < k，那么说明积分为 j 的用户无法和任何其他用户匹配，所以 dp[j] = val[j]，即积分为 j 的用户的个数。
如果 j >= k，那么说明积分为 j 的用户可能和积分为 j - k 的用户匹配，所以 dp[j] = max(dp[j - k], val[j])，即在不匹配的情况下，积分为 j 的用户的个数，和在匹配的情况下，积分为 j - k 的用户的最优解，两者取较大值。
如果 j >= 2 * k，那么说明积分为 j 的用户可能和积分为 j - k 或者 j - 2 * k 的用户匹配，所以 dp[j] = max(dp[j - k], dp[j - 2 * k] + val[j])，即在不匹配的情况下，积分为 j - k 的用户的最优解，和在匹配的情况下，积分为 j - 2 * k 的用户的最优解加上积分为 j 的用户的个数，两者取较大值。