Java 2d DP


  • 0
    D
    public class Solution {
        public int findTargetSumWays(int[] nums, int S) {
            int n = nums.length;
            if (n == 0)
                return 0;
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            if (S > sum || S < -sum)
                return 0;
            int[][] dp = new int[n][2*sum+1];
            dp[0][nums[0] + sum] += 1;
            dp[0][-nums[0] + sum] += 1;
            for (int i = 1; i < n; i++) {
                for (int j = -sum; j <= sum; j++) {
                    int k1 = j - nums[i] + sum;
                    if (k1 >= 0 && k1 <= 2*sum)
                        dp[i][j + sum] += dp[i-1][k1];
                    
                    int k2 = j + nums[i] + sum;
                    if (k2 >= 0 && k2 <= 2*sum)
                        dp[i][j + sum] += dp[i-1][k2];
                }
            }
            return dp[n-1][S + sum];
        }
    }
    

Log in to reply
 

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