0

如果给我一个正整数数组，例如 [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] 之前/之后将 nums[i] 与相应的余数添加到表中，这就像背包 DP，但是第一个版本通过了所有测试用例，而下面的一个版本对其中一些测试用例失败了。像[2,19,6,16,5,10,7,4,11,6]，它给出了81而不是正确答案84，谁能解释为什么第二个版本是错误的？

4

1 回答 1

0

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

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

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

于 2021-11-19T09:55:22.427 回答