题目内容

给小红一个长度为$n$的序列和一个整数$x$，每次操作可以选择序列中的一个元素，将其从序列中删去，或者将其值加一。问至少操作多少次，可以使操作后的序列（可以为空）中数字之和是$x$的倍数。

输入描述

第一行用两个空格隔开的正整数$n$和$x$，含义如问题描述中所述。

思路

对于这道题，可以观察到总体数据偏小，数值与倍数最大不超过1000，所以我们可以采用记忆化搜索的方式去暴力的搜索答案，首先设置数组dp[n][m],记为在操作了前n个数字之后总数字和对x取模为m到对x取模为0中间至少要多少次操作次数，实际可使用dfs来实现，其实只需要考虑是否删除某个数字，对于数字加1可以在任意数字操作，可以统一讨论

代码

def dfs(u, m):
    if u == n:
        return (x - m) % x
    if dp[u][m] != -1:
        return dp[u][m]