Java Standard dynamic programming method to solve the problem


  • 0
    M

    I wrote the code based on the dynamic programming method. I think the method is not as good as the one named "Java Solution similar to backpack problem" since the code from it is simple. However, I don't totally understand that method and the difference of thoughts behind and between these two methods. Please help me if you know the answer.

    After I paste the code here, the format is a mess.....why...

    Anyway, below is the code

    public class Solution {
    public boolean canPartition(int[] nums) {
    int sum = 0;
    int len = nums.length;
    for(int i = 0; i < len; i++){
    sum += nums[i];
    }
    if (sum % 2 == 1) return false;
    else{
    sum = sum/2;
    boolean[][] dpTable = new boolean[len + 1][sum + 1];
    for(int i = 1; i < sum + 1; i++){
    dpTable [0][i] = false;
    }
    for(int i = 0; i < len + 1; i++){
    dpTable[i][0] = true;
    }

            for(int i = 1; i <= len; i++){
                for(int j = 1; j <= sum; j++){
                    dpTable[i][j] = dpTable[i-1][j];
                    
                    if (dpTable[i][j] == false && j >= nums[i-1]){
                        dpTable[i][j] = dpTable[i-1][j - nums[i-1]];
                    }
                }
            }
            return dpTable[len][sum];
        }
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.