【Python刷题】动态规划相关问题

动态规划（Dynamic Programming，简称 DP）是一种用于解决多阶段决策最优化问题的算法策略。它通过把原问题分解为相对简单的子问题，记录子问题的解（通常使用表格等数据结构存储），避免重复计算，从而高效地解决复杂的全局最优问题。

小红取数

小红取数

算法思路

由于不同的选择组合，除以k后得到的余数也不相同，当选择一个数加上后，所得到的新值除以k后余数有可能会发生变化，而为了将这些值都能存起来并且找出最大的且余数为0的组合，我们要使用动态规划。因为能产生的余数有k中情况，于是创建一个长度为k的dp数组。j作为dp数组的索引也表示相应位置存放的数值除k后的余数，所以最终的答案一定是dp[0]上的数。动态规划的初始状态就是所有数都不选，即和为0的时候余数为0，所以dp[0]初始设为0而其余的位置设为负无穷。用num遍历数组中的每个数，然后尝试加到dp数组中的每一个值上，得到新值为dp[j]+num，很容易会想到这个新值除以k的余数为(dp[j]+num)%k。但是！如果用(dp[j]+num)%k作为索引去访问dp中的元素就出现了bug，这是因为我们初始化的时候把索引0后的位置设为了负无穷，这样导致产生了无效的索引。为了能成功访问到新值除以k后的余数所对应的位置，可以利用同余的性质，当前位置的数除以k的余数为j是规定好的，而这个数在加上num之后，他除以k后的余数就为(j+num%k)%k。接着找到余数为(j+num%k)%k的位置上的值dp[(j+num%k)%k]和dp[j]+num作比较，取较大者更新即可。而为了避免产生垃圾数据，在循环内部的操作都是在dp的副本数组上实现的，循环结束后再更新原dp数组

代码实现

n,k = map(int, input().split())
a = list(map(int, input().split()))
dp = [float('-inf')]*k
dp[0] = 0 
for num in a:new_dp = dp[:]# 复制一份dpfor j in range(k):# 遍历每个余数所对应的位置new_dp[(j+num%k)%k] = max(new_dp[(j+num%k)%k], dp[j]+num)# 如果当前余数的位置上的值加上num后得到的这个数大于这个数除k的余数的位置上的值，则更新dp = new_dp# 更新dp
print(dp[0] if dp[0] > 0 else -1)