Easiest Top-Down DP solution with explanation (Java)


  • 0
    F

    We need to memoize the intermediate steps so we don't have to recalculate them. For this we define the current state of the computation as the position that the iteration is at and the currentSum , given those two inputs to the array we can then have the dp matrix gives us the results if we have been to this state before. The other issue is that sometimes currentSum can be negative so what we do is offset where we begin in the dp matrix to the middle.

    public class TargetSum {
    
        int[][] dp;
    
        public int findTargetSumWays(int[] nums, int S) {
            dp = new int[nums.length][2000];
            int res = helper(nums, S, 0, 1000);
            return res;
        }
    
        private int helper(int[] nums, int target, int pos, int currSum) {
    
            if (pos == nums.length) {
                if (currSum - 1000 == target) {
                    return 1;
                } else {
                    return 0;
                }
            }
    
            if (dp[pos][currSum] != 0) {
                return dp[pos][currSum];
            } else {
                dp[pos][currSum] = helper(nums, target, pos + 1, currSum + nums[pos]) +
                        helper(nums, target, pos + 1, currSum - nums[pos]);
            }
    
            return dp[pos][currSum];
        }
    }
    

Log in to reply
 

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