我在保存一个动态编程问题时遇到了问题，这种问题称为分区相等子集总和

Question

很抱歉发布这个问题，但是我是dp的新手，为了获得这个概念我一直在做一些问题。在问题中，给了我一个数组，我需要告诉我是否可以将数组分为2个子集，以使它们具有相同的总和。

问题-

我在做什么-我首先计算数组的总和，如果总和不能被2整除，则返回false。否则，我继续使用背包问题的自底向上方法来解决此问题。

class Solution {
    boolean[][] dp;
    // using the knapsack problem that i know
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        // we have the sum;
        if(sum % 2 == 1){
            return false;
        }
        // else do other things
        sum = sum / 2;
        dp = new boolean[nums.length + 1][sum + 1];
        // initiation of the array
        for(int i = 0; i < dp.length; i++){
            for(int j = 0; j < dp[0].length; j++){
                if(i == 0 && j == 0){
                    dp[i][j] = true;
                }else if(i == 0){
                    dp[i][j] = false;
                }else if(j == 0){
                    dp[i][j] = true;
                }
            }
        }
        helper(nums, sum);
        for(int i = 0; i < dp.length; i++){
            for(int j = 0; j < dp[0].length; j++){
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        return dp[nums.length][sum];
    }

    // i and j are the indexes that we are trying to access right now
    public void helper(int[] nums, int sum){
        for(int i = 1; i < nums.length; i++){
            for(int j = 1; j < sum + 1; j++){
                if(nums[i - 1] <= j){
                    dp[i][j] =  dp[i][j - nums[i - 1]] || dp[i - 1][j]; 
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
    }
}

在最后打印我的dp矩阵，我得到了-

Answer 1

您错过了辅助函数for loop i < nums.length中的等式，应该为for（int i = 1; i <= nums.length; i ++）。而且，您的数组初始化不应该那么复杂。检查下面的代码是否正常

class Solution {
    boolean[][] dp;
    // using the knapsack problem that i know
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        // we have the sum;
        if(sum % 2 == 1){
            return false;
        }
        // else do other things
        sum = sum / 2;
        dp = new boolean[nums.length + 1][sum + 1];
        // initiation of the array
        for(int i = 0; i<dp.length; i++)
            dp[i][0]=true;                 // clean initialization 

        for(int i = 1; i <= nums.length; i++){ // added i==nums.length
            for(int j = 1; j <=sum ; j++){

                dp[i][j] = dp[i - 1][j];  // changed
                if(nums[i - 1] <= j){
                  dp[i][j]=dp[i-1][j-nums[i-1]]||dp[i-1][j]; 


                }
            }
        }
        return dp[nums.length][sum];
    }

}