算法面试突击手册 —— 动态规划（DP）

---

一、概念与特点

大白话 + 类比

动态规划 = 记笔记的递归

想象你要算斐波那契数列的第 50 项。如果傻傻递归，f(50) = f(49) + f(48)，f(49) = f(48) + f(47)……你会重复计算 f(48) 无数次，算到宇宙毁灭也算不完。

聪明办法：拿个小本子，算出一个记一个。下次有人问你 f(48)，直接翻本子回答——这就是记忆化搜索。再进一步，直接从小到大填表：f(0), f(1), f(2), ... 一路填到 f(50)——这就是动态规划。

DP 的核心思想就是 “大问题分解成小问题，小问题的答案记录下来复用”。

DP 做题五步法

步骤	说明	示例（爬楼梯）
1	定义状态 dp[i] 代表什么	dp[i] = 爬到第 i 阶的方法数
2	找转移方程 dp[i] = ?	dp[i] = dp[i-1] + dp[i-2]
3	初始化 dp[0], dp[1]	dp[0]=1, dp[1]=1
4	确定遍历顺序	i 从 2 到 n
5	空间优化（可选）	两个变量替代数组

识别信号词

• “最多”、“最少”、“最长”、“最大” → 最值 DP
• “方案数”、“路径数”、“多少种” → 计数 DP
• “能否”、“是否可行” → 布尔 DP
• “子序列”、“子数组”、“子串” → 序列 DP / 区间 DP
• “背包”、“分割”、“凑零钱” → 背包 DP

DP 题目分类

类型	特征	代表题
线性 DP	一维数组 dp[i]	爬楼梯、打家劫舍、最长子序列
二维网格 DP	dp[i][j] 在网格上	不同路径、最小路径和
背包 DP	选或不选，有限容量	零钱兑换、分割等和子集
区间 DP	dp[i][j] 表示区间	回文子串、戳气球
字符串 DP	两个字符串的 dp 表	编辑距离、正则匹配
状态机 DP	多个状态之间转移	买卖股票（含冷冻期）
树形 DP	在树上做 DP	打家劫舍 III

---

二、应用场景

通用模板

// 一维 DP
int[] dp = new int[n + 1];
dp[0] = 1; // 初始化
for (int i = 1; i <= n; i++) {
    dp[i] = ... ; // 转移方程
}
return dp[n];

// 二维 DP
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        dp[i][j] = ... ;
    }
}

// 空间优化：滚动数组 / 状态压缩
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
    for (int j = n; j >= 0; j--) { // 倒序！（0-1背包场景）
        dp[j] = ... ;
    }
}

---

三、Hot 100 精讲题目

---

70. Climbing Stairs 爬楼梯

📌 n 级台阶，每次爬 1 或 2 级，有多少种爬到顶的方法？如 n=3 → 3（1+1+1, 1+2, 2+1）

🔍 解题分析

核心思路：到第 n 级的方法 = 到第 n-1 级的方法 + 到第 n-2 级的方法。本质是斐波那契。

✅ 完整 Java 实现

public int climbStairs(int n) {
    if (n <= 2) return n;

    int pre2 = 1; // dp[1]
    int pre1 = 2; // dp[2]
    int cur = 0;

    for (int i = 3; i <= n; i++) {
        cur = pre1 + pre2;
        pre2 = pre1;
        pre1 = cur;
    }

    return pre1;
}

⏱ 复杂度分析

• 时间：O(n) | 空间：O(1)

💡 记忆口诀

“一次一步或两步，前两数相加”

---

198. House Robber 打家劫舍

📌 不能偷相邻的房子，求最大金额。如 [1,2,3,1] → 4（偷 1 和 3）

🔍 解题分析

状态定义：dp[i] = 考虑前 i 个房子能偷的最大金额。

转移：对第 i 个房子，要么不偷（dp[i-1]），要么偷（dp[i-2] + nums[i]）。

✅ 完整 Java 实现

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

    int pre2 = nums[0];          // dp[0]
    int pre1 = Math.max(nums[0], nums[1]); // dp[1]

    for (int i = 2; i < nums.length; i++) {
        int cur = Math.max(pre1, pre2 + nums[i]); // 不偷 vs 偷
        pre2 = pre1;
        pre1 = cur;
    }

    return pre1;
}

⏱ 复杂度分析

• 时间：O(n) | 空间：O(1)

💡 记忆口诀

“偷还是不偷，不偷继承昨天的，偷今天加前天的”

---

53. Maximum Subarray 最大子数组和

📌 找连续子数组的最大和。如 [-2,1,-3,4,-1,2,1,-5,4] → 6（[4,-1,2,1]）

🔍 解题分析

Kadane 算法：dp[i] = 以 i 结尾的最大子数组和。dp[i] = max(nums[i], dp[i-1] + nums[i])。如果前面是负数，不如重新开始。

✅ 完整 Java 实现

public int maxSubArray(int[] nums) {
    int maxSum = nums[0];
    int curSum = nums[0]; // 以当前位置结尾的最大和

    for (int i = 1; i < nums.length; i++) {
        curSum = Math.max(nums[i], curSum + nums[i]); // 接上去还是另起炉灶
        maxSum = Math.max(maxSum, curSum);
    }

    return maxSum;
}

⏱ 复杂度分析

• 时间：O(n) | 空间：O(1)

💡 记忆口诀

“前面是负就丢弃，加上自己重新算”

---

62. Unique Paths 不同路径

📌 m×n 网格，从左上到右下，每次右或下，有多少条路径？

🔍 解题分析

转移：dp[i][j] = dp[i-1][j] + dp[i][j-1]（上面的 + 左面的）。可压缩为一维数组。

✅ 完整 Java 实现

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] 是上一行的，dp[j-1] 是本行左边的
        }
    }

    return dp[n - 1];
}

⏱ 复杂度分析

• 时间：O(mn) | 空间：O(n)

💡 记忆口诀

“上面加左边，一行一行刷”

---

64. Minimum Path Sum 最小路径和

📌 m×n 网格，每次右或下，找从左上到右下的最小路径和。

🔍 解题分析

转移：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。

✅ 完整 Java 实现

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] dp = new int[n];

    dp[0] = grid[0][0];
    for (int j = 1; j < n; j++) {
        dp[j] = dp[j - 1] + grid[0][j]; // 第一行
    }

    for (int i = 1; i < m; i++) {
        dp[0] += grid[i][0]; // 第一列
        for (int j = 1; j < n; j++) {
            dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
        }
    }

    return dp[n - 1];
}

⏱ 复杂度分析

• 时间：O(mn) | 空间：O(n)

💡 记忆口诀

“当前值加上面和左面的较小者”

---

322. Coin Change 零钱兑换

📌 给定面额 coins，凑出 amount 的最少硬币数。如 coins=[1,2,5], amount=11 → 3（5+5+1）

🔍 解题分析

状态：dp[i] = 凑出 i 元的最少硬币数。

转移：dp[i] = min(dp[i - coin] + 1)，遍历所有面额。

✅ 完整 Java 实现

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1); // 初始化为"不可能"的值
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}

⏱ 复杂度分析

• 时间：O(amount × n) | 空间：O(amount)

💡 记忆口诀

“凑 i 元 = 1 + min(凑 i-coin 元)“

---

279. Perfect Squares 完全平方数

📌 找出最少数量的完全平方数（1,4,9,16…）使其和为 n。如 n=12 → 3（4+4+4）

🔍 解题分析

与零钱兑换完全一样的思路，硬币面额就是完全平方数 1,4,9,16…

✅ 完整 Java 实现

public int numSquares(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, n + 1);
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }

    return dp[n];
}

⏱ 复杂度分析

• 时间：O(n × √n) | 空间：O(n)

💡 记忆口诀

“和零钱兑换一模一样，硬币换成平方数”

---

139. Word Break 单词拆分

📌 判断字符串 s 能否被词典 wordDict 中的单词拼接而成。如 s="leetcode", wordDict=["leet","code"] → true

🔍 解题分析

状态：dp[i] = s 的前 i 个字符能否被拆分。

转移：dp[i] = dp[j] && s[j..i-1] ∈ wordDict，j 遍历所有可能的拆分点。

✅ 完整 Java 实现

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> wordSet = new HashSet<>(wordDict);
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true; // 空前缀可以拆分

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            // 前 j 个可拆分 且 后半段在词典中
            if (dp[j] && wordSet.contains(s.substring(j, i))) {
                dp[i] = true;
                break; // 找到一种即可
            }
        }
    }

    return dp[n];
}

⏱ 复杂度分析

• 时间：O(n²) | 空间：O(n)

💡 记忆口诀

“前 j 个能拆 + 后半段是单词 → 前 i 个就能拆”

---

300. Longest Increasing Subsequence 最长递增子序列

📌 找严格递增子序列的最长长度（子序列不要求连续）。如 [10,9,2,5,3,7,101,18] → 4（[2,3,7,101]）

🔍 解题分析

方法一：DP O(n²)

• dp[i] = 以 i 结尾的 LIS 长度 = max(dp[j] + 1) 对所有 j < i 且 nums[j] < nums[i]

方法二：二分贪心 O(n log n)

• 维护 tails 数组，tails[k] = 长度为 k+1 的递增子序列的最小尾元素
• 对每个 x，二分找到 tails 中第一个 >= x 的位置替换（或追加）

✅ 完整 Java 实现

// 二分贪心 O(n log n)
public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int len = 0; // tails 的有效长度

    for (int x : nums) {
        // 二分查找 tails[0..len-1] 中第一个 >= x 的位置
        int left = 0, right = len;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tails[mid] < x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        tails[left] = x; // 替换或追加
        if (left == len) len++; // 扩展了 tails
    }

    return len;
}

⏱ 复杂度分析

• 时间：O(n log n) | 空间：O(n)

💡 记忆口诀

“维护递增尾数组，二分替换小的，能扩大就扩大”

---

152. Maximum Product Subarray 乘积最大子数组

📌 找连续子数组的最大乘积。如 [2,3,-2,4] → 6（[2,3]）

🔍 解题分析

关键：乘积可能因负数而”反转”——最小的负数乘以一个负数可能变成最大的正数。所以同时维护 maxProd 和 minProd。

✅ 完整 Java 实现

public int maxProduct(int[] nums) {
    int maxProd = nums[0]; // 以当前位置结尾的最大乘积
    int minProd = nums[0]; // 以当前位置结尾的最小乘积
    int result = nums[0];

    for (int i = 1; i < nums.length; i++) {
        int n = nums[i];
        // 遇到负数，最大变最小，最小变最大
        if (n < 0) {
            int temp = maxProd;
            maxProd = minProd;
            minProd = temp;
        }

        maxProd = Math.max(n, maxProd * n);
        minProd = Math.min(n, minProd * n);

        result = Math.max(result, maxProd);
    }

    return result;
}

⏱ 复杂度分析

• 时间：O(n) | 空间：O(1)

💡 记忆口诀

“同时维护最大最小，遇负交换再比较”

---

416. Partition Equal Subset Sum 分割等和子集

📌 判断数组能否分成两个和相等的子集。如 [1,5,11,5] → true（[1,5,5] 和 [11]）

🔍 解题分析

转换：问题变成——能否选一些数使它们的和 == sum/2？这是标准的 0-1 背包。

状态：dp[j] = 能否用某些数凑出和为 j。

✅ 完整 Java 实现

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum % 2 != 0) return false; // 奇数不可能平分

    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true; // 凑 0 总是可以

    for (int num : nums) {
        // 必须倒序！避免同一个数被重复用
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }

    return dp[target];
}

⏱ 复杂度分析

• 时间：O(n × sum) | 空间：O(sum)

💡 记忆口诀

“转成 0-1 背包：选数凑 sum/2，内层倒序防重复”

---

5. Longest Palindromic Substring 最长回文子串

📌 找字符串中最长的回文子串。如 "babad" → "bab" 或 "aba"

🔍 解题分析

方法一：中心扩散（推荐，O(n²) 时间 O(1) 空间）

• 每个字符/间隙作为中心，向两边扩展

方法二：区间 DP O(n²)

• dp[i][j] = s[i..j] 是否是回文
• dp[i][j] = s[i]==s[j] && (j-i <= 2 || dp[i+1][j-1])

✅ 完整 Java 实现

// 中心扩散法
public String longestPalindrome(String s) {
    int start = 0, maxLen = 0;

    for (int i = 0; i < s.length(); i++) {
        int len1 = expand(s, i, i);     // 奇数长度中心
        int len2 = expand(s, i, i + 1); // 偶数长度中心
        int len = Math.max(len1, len2);

        if (len > maxLen) {
            start = i - (len - 1) / 2;
            maxLen = len;
        }
    }

    return s.substring(start, start + maxLen);
}

// 从 left 和 right 向两边扩展，返回回文长度
private int expand(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1; // 注意：left 和 right 多走了一步
}

⏱ 复杂度分析

• 时间：O(n²) | 空间：O(1)

💡 记忆口诀

“中心开花，两边扩展，奇偶各试一遍”

---

72. Edit Distance 编辑距离

📌 将 word1 转成 word2 的最少操作数（插入/删除/替换）。如 "horse"→"ros" → 3

🔍 解题分析

状态：dp[i][j] = word1 前 i 个字符 → word2 前 j 个字符的最少操作数。

转移：

• 字符相等：dp[i][j] = dp[i-1][j-1]
• 字符不等：dp[i][j] = 1 + min(dp[i-1][j](删), dp[i][j-1](插), dp[i-1][j-1](换))

✅ 完整 Java 实现

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] = 1 + Math.min(
                    Math.min(dp[i - 1][j], dp[i][j - 1]), // 删 / 插
                    dp[i - 1][j - 1]                      // 替换
                );
            }
        }
    }

    return dp[m][n];
}

⏱ 复杂度分析

• 时间：O(mn) | 空间：O(mn)（可优化至 O(n)）

💡 记忆口诀

“相等抄左上，不等取三角最小+1”

---

10. Regular Expression Matching 正则表达式匹配

📌 实现 . 和 * 的正则匹配。. 匹配任意单字符，* 匹配零个或多个前面的元素。

🔍 解题分析

状态：dp[i][j] = s 前 i 个字符和 p 前 j 个字符是否匹配。

转移：

• p[j-1] 是普通字母：dp[i][j] = s[i-1]==p[j-1] && dp[i-1][j-1]
• p[j-1] 是 .：dp[i][j] = dp[i-1][j-1]
• p[j-1] 是 *：
  • 不匹配（重复 0 次）：dp[i][j] = dp[i][j-2]
  • 匹配（重复 ≥1 次）：dp[i][j] = match(s[i-1], p[j-2]) && dp[i-1][j]

✅ 完整 Java 实现

public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true; // 空串匹配空模式

    // 空串匹配 a*b*c* 这种情况
    for (int j = 2; j <= n; j += 2) {
        if (p.charAt(j - 1) == '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            char pc = p.charAt(j - 1);

            if (pc == '*') {
                // 不匹配（重复 0 次）: 跳过 a*
                dp[i][j] = dp[i][j - 2];
                // 匹配（重复 ≥1 次）：当前字符对上且 s 前一个也匹配
                if (match(s.charAt(i - 1), p.charAt(j - 2))) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            } else {
                // 普通字符或 '.'
                if (match(s.charAt(i - 1), pc)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
    }

    return dp[m][n];
}

private boolean match(char sc, char pc) {
    return pc == '.' || sc == pc;
}

⏱ 复杂度分析

• 时间：O(mn) | 空间：O(mn)

💡 记忆口诀

”* 可选零次（跳过 a*）或多次（看上排），普通就配对左上”

---

121. Best Time to Buy and Sell Stock 买卖股票的最佳时机

📌 只能买卖一次，求最大利润。如 [7,1,5,3,6,4] → 5（1 买 6 卖）

🔍 解题分析

贪心：遍历时维护历史最低价，每天计算”今天卖能赚多少”。

✅ 完整 Java 实现

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE; // 历史最低买入价
    int maxProfit = 0;

    for (int price : prices) {
        minPrice = Math.min(minPrice, price);           // 更新最低价
        maxProfit = Math.max(maxProfit, price - minPrice); // 算今天卖能赚多少
    }

    return maxProfit;
}

⏱ 复杂度分析

• 时间：O(n) | 空间：O(1)

💡 记忆口诀

“记录历史最低价，每天算差价”

---

309. Best Time to Buy and Sell Stock with Cooldown 买卖股票含冷冻期

📌 多次买卖，卖出后第二天不能买（冷冻期 1 天）。求最大利润。如 [1,2,3,0,2] → 3

🔍 解题分析

状态机 DP。每天有三种状态：

• hold：持有股票
• sold：刚卖出（冷冻期）
• rest：不持有且不在冷冻期

转移：

• 今天持有 = max(昨天持有, 昨天不冷藏今天买入) → hold = max(hold, rest - price)
• 今天卖出 = 昨天持有 + 今天价格 → sold = hold + price
• 今天休息 = max(昨天休息, 昨天卖出进入冷藏) → rest = max(rest, sold)

✅ 完整 Java 实现

public int maxProfit(int[] prices) {
    int hold = Integer.MIN_VALUE; // 持有股票时的最大利润
    int sold = 0;                 // 刚卖出的最大利润
    int rest = 0;                 // 不持股且不在冷冻期的最大利润

    for (int price : prices) {
        int prevHold = hold;
        int prevSold = sold;

        hold = Math.max(prevHold, rest - price); // 保持持有 / 今天买入
        sold = prevHold + price;                  // 今天卖出
        rest = Math.max(rest, prevSold);          // 继续休息 / 昨天卖出后今天进入冷冻
    }

    return Math.max(sold, rest);
}

⏱ 复杂度分析

• 时间：O(n) | 空间：O(1)

💡 记忆口诀

“三种状态互转：hold/sold/rest，卖出后冻结一天”

---

337. House Robber III 打家劫舍 III

📌 二叉树形式的房屋，不能偷直接相连的（父子关系）。求最大金额。

🔍 解题分析

树形 DP：每个节点返回两个值 [偷这个节点的最大收益, 不偷这个节点的最大收益]。

• 偷根：root.val + 不偷左 + 不偷右
• 不偷根：max(偷左,不偷左) + max(偷右,不偷右)

✅ 完整 Java 实现

public int rob(TreeNode root) {
    int[] result = robTree(root);
    return Math.max(result[0], result[1]);
}

// 返回 [偷当前节点的最大收益, 不偷当前节点的最大收益]
private int[] robTree(TreeNode node) {
    if (node == null) return new int[]{0, 0};

    int[] left = robTree(node.left);
    int[] right = robTree(node.right);

    int robThis = node.val + left[1] + right[1];           // 偷根，子节点都不能偷
    int notRobThis = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); // 不偷根，子节点可偷可不偷

    return new int[]{robThis, notRobThis};
}

⏱ 复杂度分析

• 时间：O(n) | 空间：O(h)，递归栈

💡 记忆口诀

“每个节点返回偷与不偷，偷就不能偷儿子，不偷儿子可偷可不偷”

---

312. Burst Balloons 戳气球

📌 n 个气球排成一排，戳破 i 得 nums[i-1]*nums[i]*nums[i+1] 分，求最大总分。如 [3,1,5,8] → 167

🔍 解题分析

区间 DP。在数组两端加虚拟气球值为 1。

关键思维反转：不找”戳哪个”，而找”最后一个戳哪个”。dp[i][j] = 开区间 (i,j) 内气球全戳破的最大得分。

如果 k 是 (i,j) 内最后一个被戳破的，则 dp[i][j] = max(dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j])。

✅ 完整 Java 实现

public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] coins = new int[n + 2];
    coins[0] = coins[n + 1] = 1;
    System.arraycopy(nums, 0, coins, 1, n);

    // dp[i][j]: 开区间 (i,j) 内全戳破的最大得分
    int[][] dp = new int[n + 2][n + 2];

    // 区间长度从小到大
    for (int len = 3; len <= n + 2; len++) {
        for (int i = 0; i + len - 1 < n + 2; i++) {
            int j = i + len - 1;
            // 枚举最后一个戳破的 k
            for (int k = i + 1; k < j; k++) {
                dp[i][j] = Math.max(dp[i][j],
                    dp[i][k] + coins[i] * coins[k] * coins[j] + dp[k][j]);
            }
        }
    }

    return dp[0][n + 1];
}

⏱ 复杂度分析

• 时间：O(n³) | 空间：O(n²)

💡 记忆口诀

“反向思考：找最后一个戳的，区间 DP 填表”

---

96. Unique Binary Search Trees 不同的二叉搜索树

📌 求 1 到 n 能构成多少种不同的 BST。

🔍 解题分析

卡特兰数：dp[n] = n 个节点能构成的 BST 数量。选 i 做根，左子树有 i-1 个节点（dp[i-1] 种），右子树有 n-i 个节点（dp[n-i] 种），相乘再求和。

✅ 完整 Java 实现

public int numTrees(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1; // 空树
    dp[1] = 1; // 一个节点

    for (int i = 2; i <= n; i++) {
        for (int root = 1; root <= i; root++) {
            dp[i] += dp[root - 1] * dp[i - root]; // 左 × 右
        }
    }

    return dp[n];
}

⏱ 复杂度分析

• 时间：O(n²) | 空间：O(n)

💡 记忆口诀

“选根，左子树的种类 × 右子树的种类求和”

---

118. Pascal’s Triangle 杨辉三角

📌 生成 n 行杨辉三角。

🔍 解题分析

每行的首尾是 1，中间 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。

✅ 完整 Java 实现

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < numRows; i++) {
        List<Integer> row = new ArrayList<>();
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) row.add(1);
            else row.add(result.get(i - 1).get(j - 1) + result.get(i - 1).get(j));
        }
        result.add(row);
    }
    return result;
}

⏱ 复杂度分析

• 时间：O(n²) | 空间：O(n²)

💡 记忆口诀

“首尾是 1，中间等于肩膀上两个数相加”

---

🔜 上一章：10-回溯 | 下一章：12-贪心