Memoized Search: Top-Down Dynamic Programming

Target Sum (LeetCode 494)

Given an array nums and a target, assign a $+$ or $-$ sign to each integer to reach the target result.

Method 1: DFS with Memoization

A direct translation of the recursive logic.

Map<String, Integer> memo = new HashMap<>();

public int findTargetSumWays(int[] nums, int target) {
    return dfs(nums, 0, target);
}

private int dfs(int[] nums, int index, int remain) {
    if (index == nums.length) {
        return remain == 0 ? 1 : 0;
    }
    String key = index + "," + remain;
    if (memo.containsKey(key)) return memo.get(key);
    
    // Branch 1: Positive sign, Branch 2: Negative sign
    int ways = dfs(nums, index + 1, remain - nums[index]) + 
               dfs(nums, index + 1, remain + nums[index]);
    
    memo.put(key, ways);
    return ways;
}

Method 2: Reduction to 0/1 Knapsack (Efficient)

Mathematical transformation: Let $P$ be the sum of positive integers and $N$ be the sum of negative integers.

• $P - N = target$
• $P + N = totalSum$
• $\implies 2P = totalSum + target \implies P = (totalSum + target) / 2$

The problem becomes: How many ways can we choose a subset with sum $P$?

public int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int n : nums) sum += n;
    int s = sum + target;
    if (s < 0 || s % 2 != 0) return 0;
    
    int t = s / 2;
    int[] dp = new int[t + 1];
    dp[0] = 1;
    for (int num : nums) {
        for (int j = t; j >= num; j--) {
            dp[j] += dp[j - num];
        }
    }
    return dp[t];
}

Coin Change (Memoization Approach)

Reviewing the top-down perspective on coin selection.

Map<Integer, Integer> memo = new HashMap<>();

public int coinChange(int[] coins, int amount) {
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    if (memo.containsKey(amount)) return memo.get(amount);
    
    int minCoins = Integer.MAX_VALUE;
    for (int coin : coins) {
        int result = coinChange(coins, amount - coin);
        if (result >= 0) {
            minCoins = Math.min(minCoins, result + 1);
        }
    }
    
    int finalRes = (minCoins == Integer.MAX_VALUE) ? -1 : minCoins;
    memo.put(amount, finalRes);
    return finalRes;
}

Number of Dice Rolls with Target Sum (LeetCode 1155)

Given $n$ dice, each with $k$ faces, find the number of ways to roll a total of target.

public int numRollsToTarget(int n, int k, int target) {
    long MOD = 1_000_000_007;
    long[] dp = new long[target + 1];
    dp[0] = 1;
    
    for (int i = 0; i < n; i++) {
        long[] nextDP = new long[target + 1];
        for (int curSum = 0; curSum <= target; curSum++) {
            if (dp[curSum] == 0) continue;
            for (int face = 1; face <= k && curSum + face <= target; face++) {
                nextDP[curSum + face] = (nextDP[curSum + face] + dp[curSum]) % MOD;
            }
        }
        dp = nextDP;
    }
    return (int) dp[target];
}

Strategy Comparison Table