为什么第二版动态规划是错误的

Question

如果给我一个正整数数组，比如[2,19,6,16,5,10,7,4,11,6]，我希望找到从上述数组中可获得的最大子集总和，使总和可被 3 整除。我尝试使用动态规划

来解决它

设dp[i][j]为数组中索引i的最大和，余数为j，即 0,1,2 因为我找到了可以被 3 整除的东西。

下面我有两个实现：

        int n = nums.length;
        int[][] dp = new int[n+1][3];
        dp[0][0] = 0;
        dp[0][1] = Integer.MIN_VALUE;
        dp[0][2] = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < 3; j++) {
                int remain = nums[i-1] % 3;
                int remainder = (j + 3 - remain) % 3; 
                dp[i][j] = Math.max(dp[i-1][remainder] + nums[i-1], dp[i-1][j]); 
            }
        }
        return dp[n][0];



        int n = nums.length;
        int[][] dp = new int[n+1][3];
        dp[0][0] = nums[0] % 3 == 0 ? nums[0] : Integer.MIN_VALUE;
        dp[0][1] = nums[0] % 3 == 1 ? nums[0] : Integer.MIN_VALUE;
        dp[0][2] = nums[0] % 3 == 2 ? nums[0] : Integer.MIN_VALUE;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < 3; j++) {
                int remain = nums[i] % 3;
                int remainder = (j + 3 - remain) % 3; 
                dp[i][j] = Math.max(dp[i-1][remainder] + nums[i], dp[i-1][j]); 
            }
        }
        return dp[n-1][0] == Integer.MIN_VALUE ? 0 : dp[n-1][0];

上面的两种实现都是基于我添加或不添加 nums[i] 的事实，我将 nums[i] 添加到 table 以及我添加的相应余数 before/after nums[i]，类似于 knapsack DP，但第一个版本通过了所有测试用例，而下面的版本对其中一些测试用例失败了。比如[2,19,6,16,5,10,7,4,11,6]，给出的是81而不是正确答案84，谁能解释一下为什么第二个版本是错误的？

Answer 1

第一个版本是计算被3整除的最大子集和；第二个版本计算包含第一个元素 nums[0] 的子集的可被 3 整除的最大总和。

两个版本的唯一区别是动态规划的基本情况。第一个版本具有正确的基本情况：处理零个元素后，唯一可能的子集和为零。在第二个版本中，基本情况从 1 开始，这意味着在处理一个元素后，唯一可能的子集和是包含第一个元素的子集和。所有未来的子集总和都被迫使用该元素。

尝试运行数组 [1, 3] 上的代码。第二个版本将 return 归零，因为它不考虑没有 1.

的子集

为什么第二版动态规划是错误的

Why second version of dynamic programming is wrong

algorithm

recursion

computer-science

dynamic-programming

computer-science-theory