记忆化搜索

Map<String, Integer> memo = new HashMap<>();
// 或 int[][] memo（状态是整数时更高效）

int solve(int state1, int state2) {
    // 1. 边界
    if (baseCase) return baseValue;

    // 2. 查缓存
    String key = state1 + "," + state2;
    if (memo.containsKey(key)) return memo.get(key);

    // 3. 递归计算
    int result = 0;
    for (choice : choices) {
        result = Math.max(result, solve(nextState) + gain);
    }

    // 4. 存缓存
    memo.put(key, result);
    return result;
}

int[] memo;

int climbStairs(int n) {
    memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return dfs(n);
}

int dfs(int n) {
    if (n <= 1) return 1;
    if (memo[n] != -1) return memo[n];
    memo[n] = dfs(n - 1) + dfs(n - 2);
    return memo[n];
}

int[] memo;
int[] nums;

int lengthOfLIS(int[] nums) {
    this.nums = nums;
    memo = new int[nums.length];
    Arrays.fill(memo, -1);
    int ans = 0;
    for (int i = 0; i < nums.length; i++) {
        ans = Math.max(ans, dfs(i));
    }
    return ans;
}

// 以 nums[i] 结尾的 LIS 长度
int dfs(int i) {
    if (memo[i] != -1) return memo[i];
    int best = 1;
    for (int j = 0; j < i; j++) {
        if (nums[j] < nums[i]) {
            best = Math.max(best, dfs(j) + 1);
        }
    }
    memo[i] = best;
    return best;
}

int[] memo;
int[] coins;

int coinChange(int[] coins, int amount) {
    this.coins = coins;
    memo = new int[amount + 1];
    Arrays.fill(memo, -2); // -2 表示未计算
    return dfs(amount);
}

int dfs(int remain) {
    if (remain == 0) return 0;
    if (remain < 0) return -1;
    if (memo[remain] != -2) return memo[remain];

    int best = Integer.MAX_VALUE;
    for (int coin : coins) {
        int sub = dfs(remain - coin);
        if (sub >= 0) best = Math.min(best, sub + 1);
    }
    memo[remain] = (best == Integer.MAX_VALUE) ? -1 : best;
    return memo[remain];
}