My code is only passing 130/139 test cases using bottom up DP. What could I be doing wrong?


  • 0
    F

    One of the test case which is not passing is [1,0]. It should show 2, but my code gives 1.

    
    class Solution {
        public int findTargetSumWays(int[] nums, int S) 
        {
            
            int[][] dp = new int[2001][nums.length+1];
            int i,j,k;
            int sum=0;
            for(Integer e:nums)
            {
                sum+=e;
            }
            //Arrays.sort(nums);
            dp[sum+1000][nums.length]=1;
            dp[1000-sum][nums.length]=1;
            dp[nums[0]+1000][1]=1;
            dp[1000-nums[0]][1]=1;
            
            for(i=1;i<=nums.length;i++)
            {
                for(j=0;j<=2000;j++)
                {
                    if(dp[j][i]>0)
                    {
                        continue;
                    }
                    dp[j][i] = ((j+nums[i-1]<=2000)?(dp[j+nums[i-1]][i-1]):0) + ((j-nums[i-1]>=0)?(dp[j-nums[i-1]][i-1]):0);
                    
                }
            }
            //System.out.print(S+1000+" "+nums.length);
            if((S>1000)||(S<-1000))
            {
                return 0;
            }
            return dp[S+1000][nums.length];
        }
    }
    

Log in to reply
 

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