记忆化搜索：自顶向下的 DP

目标和（LeetCode 494）

给整数数组 nums，每个数前加 + 或 -，达到 target 的赋值方案数：

方法1：DFS + 记忆化

Map<String, Integer> memo = new HashMap<>();
public int findTargetSumWays(int[] nums, int target) {
    return dfs(nums, 0, target);
}
private int dfs(int[] nums, int i, int remain) {
    if (i == nums.length) return remain == 0 ? 1 : 0;
    String key = i + "," + remain;
    if (memo.containsKey(key)) return memo.get(key);
    int res = dfs(nums, i+1, remain - nums[i]) + dfs(nums, i+1, remain + nums[i]);
    memo.put(key, res);
    return res;
}

方法2：转化为 0/1 背包（更高效）

设正号元素和为 P，负号元素和为 N，则 P - N = target，P + N = sum，所以 P = (sum + target) / 2。问题转化为从 nums 中选若干数，使和恰好为 P 的方案数：

public int findTargetSumWays(int[] nums, int target) {
    int sum = Arrays.stream(nums).sum();
    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];
}

零钱兑换（记忆化版本回顾）

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 res = Integer.MAX_VALUE;
    for (int coin : coins) {
        int sub = coinChange(coins, amount - coin);
        if (sub >= 0) res = Math.min(res, sub + 1);
    }
    res = res == Integer.MAX_VALUE ? -1 : res;
    memo.put(amount, res);
    return res;
}

掷骰子等于目标和的方法数（LeetCode 1155）

n 个 k 面骰子，总点数为 target 的方案数（% 1e9+7）：

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[] next = new long[target + 1];
        for (int j = 0; j <= target; j++) {
            if (dp[j] == 0) continue;
            for (int face = 1; face <= k && j + face <= target; face++) {
                next[j + face] = (next[j + face] + dp[j]) % MOD;
            }
        }
        dp = next;
    }
    return (int) dp[target];
}

总结