[Algorithm] 1. 动态规划

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class ClimbingStairs {
    private int[] memo;

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

    private int climb(int n) {
        // 基本情况
        if (n == 0) return 1;
        if (n == 1) return 1;

        // 检查记忆化
        if (memo[n] != -1) return memo[n];

        // 递归计算
        int fromOneStepBack = climb(n - 1);
        int fromTwoStepsBack = climb(n - 2);

        // 存储并返回
        memo[n] = fromOneStepBack + fromTwoStepsBack;
        return memo[n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class UniquePaths {
    private int[][] memo;

    public int uniquePaths(int m, int n) {
        memo = new int[m][n];
        for (int[] row : memo) Arrays.fill(row, -1);
        return paths(m - 1, n - 1);
    }

    private int paths(int i, int j) {
        // 基本情况
        if (i == 0 || j == 0) return 1;

        // 检查记忆化
        if (memo[i][j] != -1) return memo[i][j];

        // 递归计算
        int fromTop = paths(i - 1, j);
        int fromLeft = paths(i, j - 1);

        // 存储并返回
        memo[i][j] = fromTop + fromLeft;
        return memo[i][j];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

public class UniquePathsII {
    private int[][] memo;
    private int[][] grid;

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1) return 0;

        this.grid = obstacleGrid;
        int m = grid.length;
        int n = grid[0].length;
        memo = new int[m][n];
        for (int[] row : memo) Arrays.fill(row, -1);

        return paths(m - 1, n - 1);
    }

    private int paths(int i, int j) {
        // 越界
        if (i < 0 || j < 0) return 0;

        // 障碍物
        if (grid[i][j] == 1) return 0;

        // 起始位置
        if (i == 0 && j == 0) return 1;

        // 检查记忆化
        if (memo[i][j] != -1) return memo[i][j];

        // 递归计算
        int fromTop = paths(i - 1, j);
        int fromLeft = paths(i, j - 1);

        // 存储并返回
        memo[i][j] = fromTop + fromLeft;
        return memo[i][j];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class DecodeWays {
    private int[] memo;
    private String s;

    public int numDecodings(String s) {
        this.s = s;
        memo = new int[s.length()];
        Arrays.fill(memo, -1);
        return decode(0);
    }

    private int decode(int index) {
        // 基本情况：到达末尾
        if (index == s.length()) return 1;

        // 前导零无效
        if (s.charAt(index) == '0') return 0;

        // 检查记忆化
        if (memo[index] != -1) return memo[index];

        // 选择 1：解码单个数字
        int decodeSingle = decode(index + 1);

        // 选择 2：解码两个数字（如果有效）
        int decodeDouble = 0;
        if (canDecodeTwo(index)) {
            decodeDouble = decode(index + 2);
        }

        // 存储并返回
        memo[index] = decodeSingle + decodeDouble;
        return memo[index];
    }

    private boolean canDecodeTwo(int index) {
        if (index + 1 >= s.length()) return false;
        int twoDigit = Integer.parseInt(s.substring(index, index + 2));
        return twoDigit >= 10 && twoDigit <= 26;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class Fibonacci {
    private int[] memo;

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

    private int calculate(int n) {
        // 基本情况
        if (n == 0) return 0;
        if (n == 1) return 1;

        // 检查记忆化
        if (memo[n] != -1) return memo[n];

        // 递归计算
        int fromPrevOne = calculate(n - 1);
        int fromPrevTwo = calculate(n - 2);

        // 存储并返回
        memo[n] = fromPrevOne + fromPrevTwo;
        return memo[n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class CountSortedVowelStrings {
    private int[][] memo;

    public int countVowelStrings(int n) {
        // 5 个元音：a(0), e(1), i(2), o(3), u(4)
        memo = new int[n + 1][5];
        for (int[] row : memo) Arrays.fill(row, -1);
        return count(n, 0);
    }

    private int count(int n, int startVowel) {
        // 基本情况
        if (n == 1) return 5 - startVowel;

        // 检查记忆化
        if (memo[n][startVowel] != -1) return memo[n][startVowel];

        // 从当前元音开始求和所有选择
        int total = 0;
        for (int v = startVowel; v < 5; v++) {
            total += chooseVowel(n, v);
        }

        // 存储并返回
        memo[n][startVowel] = total;
        return memo[n][startVowel];
    }

    private int chooseVowel(int n, int vowel) {
        return count(n - 1, vowel);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class MinCostClimbingStairs {
    private int[] memo;
    private int[] cost;

    public int minCostClimbingStairs(int[] cost) {
        this.cost = cost;
        int n = cost.length;
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return minCost(n);
    }

    private int minCost(int step) {
        // 基本情况
        if (step == 0) return 0;
        if (step == 1) return 0;

        // 检查记忆化
        if (memo[step] != -1) return memo[step];

        // 选择 1：从 1 步之前
        int costFrom1Back = minCost(step - 1) + cost[step - 1];

        // 选择 2：从 2 步之前
        int costFrom2Back = minCost(step - 2) + cost[step - 2];

        // 存储并返回最小值
        memo[step] = Math.min(costFrom1Back, costFrom2Back);
        return memo[step];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public class HouseRobber {
    private int[] memo;
    private int[] nums;

    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        this.nums = nums;
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return maxRob(nums.length - 1);
    }

    private int maxRob(int i) {
        // 基本情况
        if (i == 0) return nums[0];
        if (i == 1) return Math.max(nums[0], nums[1]);

        // 检查记忆化
        if (memo[i] != -1) return memo[i];

        // 选择 1：跳过这个房子
        int skipHouse = maxRob(i - 1);

        // 选择 2：抢劫这个房子
        int robHouse = nums[i] + maxRob(i - 2);

        // 存储并返回最大值
        memo[i] = Math.max(skipHouse, robHouse);
        return memo[i];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public class CoinChange {
    private int[] memo;
    private int[] coins;

    public int coinChange(int[] coins, int amount) {
        this.coins = coins;
        memo = new int[amount + 1];
        Arrays.fill(memo, -1);

        int result = minCoins(amount);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private int minCoins(int amount) {
        // 基本情况
        if (amount == 0) return 0;
        if (amount < 0) return Integer.MAX_VALUE;

        // 检查记忆化
        if (memo[amount] != -1) return memo[amount];

        // 尝试每个硬币
        int minCount = Integer.MAX_VALUE;
        for (int coin : coins) {
            int subResult = useCoin(amount, coin);
            if (subResult != Integer.MAX_VALUE) {
                minCount = Math.min(minCount, 1 + subResult);
            }
        }

        // 存储并返回
        memo[amount] = minCount;
        return memo[amount];
    }

    private int useCoin(int amount, int coin) {
        return minCoins(amount - coin);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public class LongestIncreasingSubsequence {
    private int[] memo;
    private int[] nums;

    public int lengthOfLIS(int[] nums) {
        this.nums = nums;
        memo = new int[nums.length];
        Arrays.fill(memo, -1);

        int maxLength = 0;
        for (int i = 0; i < nums.length; i++) {
            maxLength = Math.max(maxLength, lis(i));
        }
        return maxLength;
    }

    private int lis(int i) {
        // 基本情况
        if (memo[i] != -1) return memo[i];

        // 从长度 1 开始（仅此元素）
        int maxLen = 1;

        // 尝试从先前元素扩展
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                maxLen = Math.max(maxLen, extendFrom(j));
            }
        }

        // 存储并返回
        memo[i] = maxLen;
        return memo[i];
    }

    private int extendFrom(int j) {
        return lis(j) + 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class LongestCommonSubsequence {
    private int[][] memo;
    private String text1, text2;

    public int longestCommonSubsequence(String text1, String text2) {
        this.text1 = text1;
        this.text2 = text2;
        memo = new int[text1.length()][text2.length()];
        for (int[] row : memo) Arrays.fill(row, -1);

        return lcs(text1.length() - 1, text2.length() - 1);
    }

    private int lcs(int i, int j) {
        // 基本情况
        if (i < 0 || j < 0) return 0;

        // 检查记忆化
        if (memo[i][j] != -1) return memo[i][j];

        // 如果字符匹配
        if (text1.charAt(i) == text2.charAt(j)) {
            memo[i][j] = matchChars(i, j);
        } else {
            // 如果它们不匹配
            memo[i][j] = skipChar(i, j);
        }

        return memo[i][j];
    }

    private int matchChars(int i, int j) {
        return 1 + lcs(i - 1, j - 1);
    }

    private int skipChar(int i, int j) {
        int skipI = lcs(i - 1, j);
        int skipJ = lcs(i, j - 1);
        return Math.max(skipI, skipJ);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public class MaximumSubarray {
    private int[] memo;
    private int[] nums;

    public int maxSubArray(int[] nums) {
        this.nums = nums;
        memo = new int[nums.length];
        Arrays.fill(memo, Integer.MIN_VALUE);

        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            maxSum = Math.max(maxSum, maxEndingAt(i));
        }
        return maxSum;
    }

    private int maxEndingAt(int i) {
        // 基本情况
        if (i == 0) return nums[0];

        // 检查记忆化
        if (memo[i] != Integer.MIN_VALUE) return memo[i];

        // 选择 1：重新开始
        int startFresh = nums[i];

        // 选择 2：扩展先前的
        int extendPrev = nums[i] + maxEndingAt(i - 1);

        // 存储并返回最大值
        memo[i] = Math.max(startFresh, extendPrev);
        return memo[i];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public class WordBreak {
    private Boolean[] memo;
    private String s;
    private Set<String> wordSet;

    public boolean wordBreak(String s, List<String> wordDict) {
        this.s = s;
        this.wordSet = new HashSet<>(wordDict);
        memo = new Boolean[s.length()];
        return canBreak(0);
    }

    private boolean canBreak(int start) {
        // 基本情况
        if (start == s.length()) return true;

        // 检查记忆化
        if (memo[start] != null) return memo[start];

        // 尝试每个单词
        for (String word : wordSet) {
            if (tryWord(start, word)) {
                memo[start] = true;
                return true;
            }
        }

        // 没有单词有效
        memo[start] = false;
        return false;
    }

    private boolean tryWord(int start, String word) {
        int end = start + word.length();
        if (end > s.length()) return false;
        if (!s.substring(start, end).equals(word)) return false;
        return canBreak(end);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

public class PartitionEqualSubsetSum {
    private Boolean[][] memo;
    private int[] nums;

    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) totalSum += num;

        // 如果总和是奇数，则无法平均分割
        if (totalSum % 2 != 0) return false;

        this.nums = nums;
        int target = totalSum / 2;
        memo = new Boolean[nums.length][target + 1];

        return canAchieve(0, target);
    }

    private boolean canAchieve(int i, int sum) {
        // 基本情况
        if (sum == 0) return true;
        if (i >= nums.length || sum < 0) return false;

        // 检查记忆化
        if (memo[i][sum] != null) return memo[i][sum];

        // 选择 1：包括当前数字
        boolean include = includeNum(i, sum);

        // 选择 2：排除当前数字
        boolean exclude = excludeNum(i, sum);

        // 存储并返回
        memo[i][sum] = include || exclude;
        return memo[i][sum];
    }

    private boolean includeNum(int i, int sum) {
        return canAchieve(i + 1, sum - nums[i]);
    }

    private boolean excludeNum(int i, int sum) {
        return canAchieve(i + 1, sum);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public class TargetSum {
    private Map<String, Integer> memo;
    private int[] nums;
    private int target;

    public int findTargetSumWays(int[] nums, int target) {
        this.nums = nums;
        this.target = target;
        memo = new HashMap<>();
        return countWays(0, 0);
    }

    private int countWays(int i, int currentSum) {
        // 基本情况
        if (i == nums.length) {
            return currentSum == target ? 1 : 0;
        }

        // 检查记忆化
        String key = i + "," + currentSum;
        if (memo.containsKey(key)) return memo.get(key);

        // 选择 1：加上当前数字
        int addWays = addNum(i, currentSum);

        // 选择 2：减去当前数字
        int subtractWays = subtractNum(i, currentSum);

        // 存储并返回总和
        int totalWays = addWays + subtractWays;
        memo.put(key, totalWays);
        return totalWays;
    }

    private int addNum(int i, int currentSum) {
        return countWays(i + 1, currentSum + nums[i]);
    }

    private int subtractNum(int i, int currentSum) {
        return countWays(i + 1, currentSum - nums[i]);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public class CanJump {
    private Boolean[] memo;
    private int[] nums;

    public boolean canJump(int[] nums) {
        this.nums = nums;
        memo = new Boolean[nums.length];
        return canReachEnd(0);
    }

    private boolean canReachEnd(int pos) {
        // 基本情况：到达末尾
        if (pos >= nums.length - 1) return true;

        // 检查记忆化
        if (memo[pos] != null) return memo[pos];

        // 尝试所有可能的跳跃
        int maxJump = nums[pos];
        for (int jump = 1; jump <= maxJump; jump++) {
            if (tryJump(pos, jump)) {
                memo[pos] = true;
                return true;
            }
        }

        // 没有跳跃有效
        memo[pos] = false;
        return false;
    }

    private boolean tryJump(int pos, int jump) {
        return canReachEnd(pos + jump);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class PerfectSquares {
    private int[] memo;

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

    private int minSquares(int n) {
        // 基本情况
        if (n == 0) return 0;

        // 检查记忆化
        if (memo[n] != -1) return memo[n];

        // 尝试所有 <= n 的完全平方数
        int minCount = Integer.MAX_VALUE;
        for (int i = 1; i * i <= n; i++) {
            int count = useSquare(n, i);
            minCount = Math.min(minCount, count);
        }

        // 存储并返回
        memo[n] = minCount;
        return memo[n];
    }

    private int useSquare(int n, int i) {
        return 1 + minSquares(n - i * i);
    }
}