可被三整除的最大和「变题」

1262. 可被三整除的最大和

其实这是一个 0-1 背包问题，关于「0-1 背包」可见 经典动态规划：0-1 背包问题

对于每个数，都有两种选择：选择它 or 不选它

先给出dp[i][j]的定义：对于前i个数，当前余数为j，这种情况下背包最大和就是dp[i][j]

这里需要强调一下：假设选择某个数，记为a，其余数记为x = n % 3，那么前一状态就是dp[i - 1][(j - x + 3) % 3]

xxxxxxxxxx
public int maxSumDivThree(int[] nums) {
    int n = nums.length;
    int[][] dp = new int[n + 1][3];
    // base case: 0 个数，余数大于 0 时，和赋值为最小值
    dp[0][1] = Integer.MIN_VALUE;
    dp[0][2] = Integer.MIN_VALUE;
    for (int i = 1; i <= n; i++) {
        // nums[i - 1] 的余数
        int x = nums[i - 1] % 3;
        for (int j = 0; j < 3; j++) {
            // dp[i - 1][j]: 表示不选
            // dp[i - 1][(j - x + 3) % 3] + nums[i - 1]: 表示选择
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][(j - x + 3) % 3] + nums[i - 1]);
        }
    }
    return dp[n][0];
}

变题：可被 k 整除的最大和

不说废话，直接给出通解：

public int maxSumDivK(int[] nums, int k) {
    int n = nums.length;
    int[][] dp = new int[n + 1][k];
    // base case: 0 个数，余数大于 0 时，和赋值为最小值
    for (int i = 1; i < k; i++) dp[0][i] = Integer.MIN_VALUE;
    for (int i = 1; i <= n; i++) {
        // nums[i - 1] 的余数
        int x = nums[i - 1] % k;
        for (int j = 0; j < k; j++) {
            // dp[i - 1][j]: 表示不选
            // dp[i - 1][(j - x + k) % k] + nums[i - 1]: 表示选择
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][(j - x + k) % k] + nums[i - 1]);
        }
    }
    return dp[n][0];
}