对局匹配
最近遇到这样一道题目：
小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。
小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是K的两名用户匹配在一起。如果两人分差小于或大于K，系统都不会将他们匹配。
现在小明知道这个网站总共有N名用户，以及他们的积分分别是A1, A2, ... AN。
小明想了解最多可能有多少名用户同时在线寻找对手，但是系统却一场对局都匹配不起来(任意两名用户积分差不等于K)？
输入
第一行包含两个个整数N和K。
第二行包含N个整数A1, A2, ... AN。
对于30%的数据，1 <= N <= 10
对于100%的数据，1 <= N <= 100000, 0 <= Ai <= 100000, 0 <= K <= 100000
输出
一个整数，代表答案。
样例输入
10 0
1 4 2 8 5 7 1 4 2 8
样例输出
6刚拿到这道题，我的第一感觉就是这是一道动态规划类型的题目。为什么这么说呢，因为当我们求出最多有k个人的时候，如果想求k+1人是否可行的话，必然会存在很多的重复计算，再加之直觉的判断，我断定它是一道动态规划的题目。仅仅做到这一点还远远不够，仔细分析题目，会发现这个题目和以前求leetcode打家劫舍问题有点类似，但是却又不太一样。
本题的关键在于“系统却一场对局都匹配不起来(任意两名用户积分差不等于K)”这个条件，即任意两个相隔为k的用户不能够同时上线。题中给出的数据是N个用户的分数数据，并不能直接看出本题的状态转移。因此，在分析本题的状态转移之前，我们要对原始数据进行一定的处理。
数据预处理
由于条件是任意两个差值为k的用户都不能同时存在，本题其实就是在求不同分值同时在线的情况，即相同分值的用户是等效的。因此，我们可以先将用户按照分数统计出来并分类。我们用一个MAX_SCORE大小的数据来记录即可。现在我们得到了所有用户的分数统计。下一步，我们将相互排斥的用户分到一组然后利用dp求取最优解。即：
{0, k, 2k, 3k...} 相互排斥的用户分为一组，利用dp求最优解。
{1, k+1, 2k+1, 3k+1...} 任意两组之间的用户不排斥，因此最终答案是每组的最优解相加即可
{2, k+2, 2k+2, 3k+2...}
...
{k-1, k+k-1, 2k+k-1, 3k+k-1...}对数据处理完毕，接下来我们就可以对每组数据进行动态规划了。
动态规划
对于动态规划问题，我们还是按照前文的方法来做，一步一步进行分析。
明确dp数组含义
我们要求解的问题是当前组能够同时上线的用户数量，所以我们的dp数组含义就应该是当前最大用户数量。因此dp[i]定义为val[0…i]的最大用户数量。
明确当前的选择
当我们把问题缩小到每一组时，我们可以发现这个问题的本质条件就是每一组相邻的两个分数不能同时选择，这里就和打家劫舍问题类似了，因此当前的选择也很简单，就是是否选择当前的分数；如果选择了当前分数，就不能选择前一个dp[i] = dp[i-2]+val[i], 若不选择就是dp[i] = dp[i-1]。
状态转移方程
这里状态转移方程就很容易给出了：dp[i] = max(dp[i-2]+val[i], dp[i-1])
base case
本题的base case就是第一个的时候，由于没有选择，dp[0] = [0]
代码实现
至此，问题的核心就分析完毕了，下面给出代码实现，具体细节在注释中阐述。
MAX_SCORE = 10000+5
MAXN = 10000+5
cnt = [0] * MAXSCORE
val = [0] * MAXN
dp = [0] * MAXN
ans = 0 # 最终答案
#对应蓝桥杯数据输入部分
tmp = input().split()
n, k = int(tmp[0]), int(tmp[1])
tmp = input().split()
# 数据预处理
for i in range(n):
cnt[int(tmp[i])] += 1
# k=0的情况特殊处理
if k == 0:
for i in range(MAX_SCORE):
if cnt[i]:
ans += 1
else:
for i in range(k):
m = 0 #每一组个数的计数变量
for j in range(i, MAX_SCORE, k): #将当前一组的数据单独拿出来 即分组操作
val[m] = cnt[j] # val 中存储的就是当前组的数据
m += 1
dp[0] = val[0] # base case
for j in range(1, m): # 状态转移
if j == 1:
dp[j] = max(dp[0], val[j])
else:
dp[j] = max(dp[j-1], dp[j-2]+val[j]) # 状态转移方程
ans += dp[m-1] # 每组的最优解累加
print(ans)小结
这道题本身的动态规划过程并不困难，主要难点在于如何想到利用动态规划的方法来解决问题。又由于本题并不是直接的动态规划类的题目，需要进行一定处理才可以利用动态规划来解决。这也就说用需要对问题进行合理的转化。
