Plantre
plantre
2025-06-12
目录

动态规划

# 322. 零钱兑换 - 力扣（LeetCode） (opens new window)

# 🔄 两种循环方式的对比

特性 方式一：外层金额→内层硬币 方式二：外层硬币→内层金额
循环结构 for (int i = 1; i <= amount; i++) for (int coin : coins) for (int coin : coins) for (int j = coin; j <= amount; j++)
适用场景 求最小值问题（如零钱兑换） 完全背包问题的最优解（组合数、最小值）
效率 可能重复无效计算（需判断 i >= coin） 内层循环从 coin 开始，避免无效计算，更高效
优化空间 需额外条件判断，代码略冗余 无需条件判断，逻辑更简洁
动态规划类型 更接近“排列”思路（但本题不强调顺序） 更符合“组合”思路（完全背包标准解法）
class Solution {
    public int coinChange(int[] coins, int amount) {
        // 处理边界：总金额为0时无需硬币
        if (amount == 0) {
            return 0;
        }
        // dp[i] 表示凑齐金额 i 所需的最少硬币数
        int[] dp = new int[amount + 1];
        // amount + 1 被用作一个​​比所有可能解都大的值​​（上界）
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        // 动态规划：遍历每个硬币
        for(int coin : coins) {
            // 从当前硬币面值开始更新dp数组
            for(int j = coin; j <= amount; j++){
                // 状态转移：取「不选当前硬币」和「选当前硬币」的最小值
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }
        // 若dp[amount]未被更新，说明无解
        return dp[amount] > amount ? -1 : dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
		for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                // 可能重复无效计算（需判断 i >= coin）
                if (i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
1
2
3
4
5
6
7
8

# 70. 爬楼梯 - 力扣（LeetCode） (opens new window)

class Solution {
    public int climbStairs(int n) {
        if (n <= 1) return 1;
        int[] dp = new int[n + 1];
        dp[0] = 1; // 边界：地面
        dp[1] = 1; // 边界：第1阶
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int climbStairs(int n) {
        if (n <= 1) return 1;
        // 对应 dp[0]
        int prev = 1;
        // 对应 dp[1]
        int curr = 1;
        for(int i = 2; i <= n; i++) {
            int next = prev + curr;
            prev = curr;
            curr = next;
        }
        return curr;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 198. 打家劫舍 - 力扣（LeetCode） (opens new window)

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            // 偷​​：收益 = 前 i-2 间房屋的最大收益 + nums[i]（因不能偷相邻的 i-1）
            // ​​不偷​​：收益 = 前 i-1 间房屋的最大收益
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 62. 不同路径 - 力扣（LeetCode） (opens new window)

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

优化版（暂时没懂）

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1); // 第一行全为1
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] = dp[j] + dp[j-1]; // dp[j] 更新为当前行
            }
        }
        return dp[n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 64. 最小路径和 - 力扣（LeetCode） (opens new window)

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        // 初始化第一行和第一列
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        // 填充剩余网格
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

空间优化版

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        // 填充剩余网格, i,j从0开始
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                else if (i == 0) grid[i][j] += grid[i][j-1];
                else if (j == 0) grid[i][j] += grid[i-1][j];
                else grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
            }
        }
        return grid[m-1][n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 1143. 最长公共子序列 - 力扣（LeetCode） (opens new window)

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 5. 最长回文子串 - 力扣（LeetCode） (opens new window)

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int ans = 1; // 最长回文子串的长度，擂台
        int leftIndex = 0, rightIndex = 0; // 最长回文子串的左，右位置
        boolean[][] dp = new boolean[n][n]; // dp[i][j],i->j的串是否回文
        // 初始化长度为1的回文子串
        for (int i = 0;i < s.length(); i++) {
            dp[i][i] = true;
        }
        // 初始化长度为2的回文子串
        for (int i = 0; i + 1 < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                if (ans < 2) {
                    ans = 2;
                    leftIndex = i;
                    rightIndex = i + 1;
                }
            } 
        }
        // 遍历长度大于2的回文子串
        for (int len = 3; len <= s.length(); len++) {
            for (int left = 0; left < s.length(); left++) {
                int right = left + len - 1;
                if (right >= s.length()) break;
                if (s.charAt(left) == s.charAt(right) && dp[left + 1][right -1]) {
                    dp[left][right] = true;
                    if (len > ans) {
                        ans = len;
                        leftIndex = left;
                        rightIndex = right;
                    }
                }
            }
        }
        return s.substring(leftIndex, rightIndex + 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

# 53. 最大子数组和 - 力扣（LeetCode） (opens new window)

dp 数组的含义：以 nums[i] 为结尾的「最⼤⼦数组和」为 dp[i]

dp[i] 有两种「选择」，要么与前⾯的相邻⼦数组连接，形成⼀个和更⼤的⼦数组；要么不与前⾯的⼦数组连接，⾃成⼀派，⾃⼰作为⼀个⼦数组。

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int[] dp = new int[n];
        // base case
        dp[0] = nums[0];
        // 状态转移⽅程
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 152. 乘积最大子数组 - 力扣（LeetCode） (opens new window)

class Solution {
    public int maxProduct(int[] nums) {
        int maxVal = nums[0], minVal = nums[0], res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 保存旧最大值
            int preMax = maxVal;
            // 情况1：maxVal * nums[i];延续之前的最大值
            // 情况2：minVal * nums[i];最小值可能因负数翻转成最大值
            maxVal = Math.max(nums[i], Math.max(maxVal * nums[i], minVal * nums[i]));
            // 情况1：minVal * nums[i];延续之前的最小值
            // 情况2：preMax * nums[i];之前的最大值可能因负数翻转成最小值
            minVal = Math.min(nums[i], Math.min(minVal * nums[i], preMax * nums[i]));
            res = Math.max(res, maxVal);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 718. 最长重复子数组 - 力扣（LeetCode） (opens new window)

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        //dp[i][j] 的含义​​：以 nums1[i-1] 结尾的子数组和以 nums2[j-1] 结尾的子数组的​​最长公共后缀长度
        int[][] dp = new int[m + 1][n + 1];
        int result = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    result = Math.max(result, dp[i][j]);
                }
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

空间优化版本（没看懂）

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        // 一维数组替代二维
        int[] dp = new int[nums2.length + 1];
        int result = 0;
        for (int i = 1; i <= nums1.length; i++) {
            // 倒序避免覆盖
            for (int j = nums2.length; j >= 1; j--) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                    result = Math.max(result, dp[j]);
                } else {
                    // 需显式重置0
                    dp[j] = 0;
                }
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 300. 最长递增子序列 - 力扣（LeetCode） (opens new window)

$$ dp[i] = \begin{cases} 1 & \text{（初始值，自身作为子序列）} \ \max{dp[j] + 1 \mid 0 \le j < i, \text{nums}[j] < \text{nums}[i]} & \text{（存在可接续的前驱）} \end{cases} $$

class Solution {
    public int lengthOfLIS(int[] nums) {
        // dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
        int[] dp = new int[nums.length];
        // base case：dp 数组全都初始化为 1
        Arrays.fill(dp, 1);
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 72. 编辑距离 - 力扣（LeetCode） (opens new window)

$$ dp[i][j] = \begin{cases} dp[i-1][j-1] & \text{if } \text{word1}[i-1] = \text{word2}[j-1] \ \min(dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + 1) & \text{otherwise} \end{cases} $$

当比较 word1[i-1] 和 word2[j-1] 时，分两种情况：

# 1. 字符匹配（无需操作）

  • 若 word1[i-1] == word2[j-1]： 当前字符已相同，无需额外操作，直接继承子问题解： dp[i][j] = dp[i-1][j-1]。

# 2. 字符不匹配（三种操作选择最小值）

若字符不等，需选择插入、删除或替换中的最小代价操作：

  • 插入操作： 在 word1 中插入 word2[j-1]，使 word1[0..i-1] + 新字符 → word2[0..j-1]。 子问题转化为 dp[i][j-1]（word1 的前 i 个字符 → word2 的前 j-1 个字符），再加插入操作成本 1： cost_insert = dp[i][j-1] + 1。
  • 删除操作： 删除 word1[i-1]，使 word1[0..i-2] → word2[0..j-1]。 子问题转化为 dp[i-1][j]，再加删除成本 1： cost_delete = dp[i-1][j] + 1。
  • 替换操作： 将 word1[i-1] 替换为 word2[j-1]，使两字符串末尾字符相同。 子问题转化为 dp[i-1][j-1]，再加替换成本 1： cost_replace = dp[i-1][j-1] + 1。

状态转移方程： dp[i][j] = min(cost_insert, cost_delete, cost_replace)

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        for (int i = 1 ; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 139. 单词拆分 - 力扣（LeetCode） (opens new window)

动态规划

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        // dp[i] 表示字符串 s 的前 i 个字符（即 s[0..i-1]）能否被拆分
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        } 
        return dp[s.length()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

回溯法 + 记忆化搜索

class Solution {

    private Set<String> wordSet;
    private int[] memo;  // 0:未计算, 1:可拆分, -1:不可拆分

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

    private boolean backtrack(String s, int start) {
        if (start == s.length()) return true;
        if (memo[start] != 0) return memo[start] == 1;
        for (int end = start + 1; end <= s.length(); end++) {
            String  word = s.substring(start, end);
            if (wordSet.contains(word) && backtrack(s, end)) {
                memo[start] = 1;
                return true;
            }
        }
        memo[start] = -1;
        return false;
    }

}
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

# 股票专题

dp[i][k][0i or 1]
i是天数，k是允许交易的最大次数，第三个是当前的持有状态(1 表示持有，0 表示没有持有)
    dp本身的值表示手中的钱
dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易
1
2
3
4

# 121. 买卖股票的最佳时机 - 力扣（LeetCode） (opens new window)

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
今天是第i天，我现在手上没有持有股票 = max (昨天也没持有，昨天持有但卖掉了)
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
今天是第i天，我现在手上有股票 = max (昨天也持有，昨天没持有但买入了)  
    
// 不持有股票的状态转移
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            ↑（保持不持有）    ↑（卖出股票实现利润）

// 持有股票的状态转移（以单次交易为例）
dp[i][1] = max(dp[i-1][1], -prices[i])
            ↑（保持持有）    ↑（新买入，利润未实现）
    dp[i][1] = Math.max(dp[i-1][1], -prices[i])为什么是-prices[i]而不是dp[i-1][0]-prices[i]？
    若第 i 天​​新买入股票​​，由于只能交易一次，此前不能有交易，因此买入前的利润为 0，成本为 -prices[i]
    若沿用前一天的状态（dp[i-1][1]），表示之前已买入且未卖出
    -prices[i] 直接表示首次买入的成本，与 dp[i-1][0] 无关，因为 dp[i-1][0] 可能包含历史交易（但单次交易不允许历史操作）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        for (int i = 0; i < n; i++ ) {
            if (i - 1 == -1) {
                // base case
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], 0 - prices[i]);
        } 
        return dp[n - 1][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 122. 买卖股票的最佳时机 II - 力扣（LeetCode） (opens new window)

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
1
2
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        for (int i = 0; i < n; i++ ) {
            if (i - 1 == -1) {
                // base case
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
        } 
        return dp[n - 1][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode） (opens new window)

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。
    
    
    # 持有股票：延续持仓 或 冷冻期后买入
dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])
# 冷冻期：仅由前一天卖出触发
dp[i][1] = dp[i-1][0] + prices[i]
# 非冷冻期：延续冷冻期或非冷冻期
dp[i][2] = max(dp[i-1][1], dp[i-1][2])
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n <= 1) return 0; // 无法交易
        
        int[][] dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                // Base Case 1: 第一天
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            if (i == 1) {
                // Base Case 2: 第二天
                dp[i][0] = Math.max(dp[0][0], dp[0][1] + prices[1]);
                dp[i][1] = Math.max(dp[0][1], -prices[1]); // 不受冷冻期限制
                continue;
            }
            // 状态转移
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]); // 跳过冷冻期
        }
        return dp[n - 1][0]; // 最终利润一定是不持有股票
    }
}
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
编辑 (opens new window)
上次更新: 2025/07/25, 12:08:10
回溯
二叉树

← 二叉树→

最近更新
01
加油鸭
07-30
02
要点总结
07-28
03
字符串
07-15
更多文章>
Theme by Vdoing | Copyright © 2025-2025 plantre | MIT License