跳至主要內容

动态规划从入门到精通

老张2026/4/18大约 21 分钟算法动态规划DP背包问题LeetCode

动态规划从入门到精通

动态规划（Dynamic Programming，DP）是算法面试中出现频率最高、也是最难掌握的专题之一。它的核心思想是：将大问题拆解为若干重叠子问题，利用已计算的子问题结果避免重复运算。本文从解题框架出发，配合可视化表格和状态转移图，带你系统掌握 DP 的各个子类型。

一、DP 解题五步法

拿到任何一道 DP 题，按照以下五步走，思路清晰不迷茫：

记忆口诀：定义 → 方程 → 初始值 → 顺序 → 验证，缺一不可。

二、一维 DP

2.1 爬楼梯（LC 70）— 斐波那契模型

题目：每次可以爬 1 或 2 级台阶，爬 n 级有多少种方法？

状态定义：dp[i] = 爬到第 i 级台阶的方法总数

转移方程：dp[i] = dp[i-1] + dp[i-2]

初始值：dp[1] = 1，dp[2] = 2

下面用交互动画模拟 n=6 时 dp 数组的逐步填充过程：

📊 DP 填充过程演示

初始化：dp[0]=1（0级台阶有1种方法），dp[1]=1（跨1步，只有1种方法）
dp[0]dp[1]dp[2]dp[3]dp[4]dp[5]dp[6]
011
1 / 6
// LC 70 爬楼梯 - Java 实现
public int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
// 空间优化：只保留前两个变量，O(1) 空间
public int climbStairsOpt(int n) {
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

2.2 打家劫舍（LC 198）

题目：相邻两间房不能同时抢，求最大收益。

状态定义：dp[i] = 抢到第 i 间房时的最大收益

转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i])

下面是状态转移的两种决策：

// LC 198 打家劫舍 - Java 实现
public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    int[] dp = new int[n];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[n - 1];
}

2.3 最长递增子序列（LC 300）—— LIS

状态定义：dp[i] = 以 nums[i] 结尾的最长递增子序列长度

转移方程：dp[i] = max(dp[j] + 1)，其中 j < i 且 nums[j] < nums[i]

O(n log n) 二分优化：维护一个 tails 数组，tails[i] 存储长度为 i+1 的递增子序列末尾最小值，每次用二分查找定位插入位置。

📊 DP 填充过程演示

以 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例，展示 dp[i]（以 nums[i] 结尾的 LIS 长度）逐步计算过程：

i=0，nums[0]=10，前面没有比10小的，dp[0]=1
1 / 8
// LC 300 LIS - O(nlogn) 二分优化
public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int num : nums) {
        int lo = 0, hi = size;
        // 二分找第一个 >= num 的位置
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (tails[mid] < num) lo = mid + 1;
            else hi = mid;
        }
        tails[lo] = num;
        if (lo == size) size++;
    }
    return size;
}

tails 不是实际子序列，但 size 就是 LIS 的长度。这是经典的"贪心 + 二分"技巧。

三、二维 DP

3.1 最小路径和（LC 64）

题目：从左上角到右下角，只能向右或向下，求路径上数字之和的最小值。

状态定义：dp[i][j] = 到达格子 (i,j) 的最小路径和

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

以下以 3×3 网格 [[1,3,1],[1,5,1],[4,2,1]] 为例，模拟逐格填充：

原始 grid，目标：从左上到右下，只能向右或向下移动
j=0j=1j=2
i=0131
i=1151
i=2421
1 / 6
// LC 64 最小路径和 - Java 实现
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 j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
    for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
    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];
}

3.2 不同路径（LC 62）

状态定义：dp[i][j] = 到达 (i,j) 的路径数

转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]

// LC 62 不同路径
public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    // 第一行和第一列全为 1
    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];
}

3.3 最长公共子序列（LC 1143）—— LCS

状态定义：dp[i][j] = text1[0..i-1] 与 text2[0..j-1] 的最长公共子序列长度

转移方程：

  • 若 text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
  • 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

以 text1 = "ace"，text2 = "abcde" 为例，逐格填充 DP 表：

📊 DP 填充过程演示

初始化：第0行和第0列全部置0（空串与任何串的LCS=0）
abcde
000000
a0
c0
e0
1 / 6
// LC 1143 最长公共子序列 - Java 实现
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];
}

3.4 编辑距离（LC 72）

状态定义：dp[i][j] = 将 word1[0..i-1] 转换为 word2[0..j-1] 所需的最少操作数

三种操作及其转移：

操作含义转移
插入在 word1 中插入一个字符dp[i][j-1] + 1
删除删除 word1 中一个字符dp[i-1][j] + 1
替换替换 word1 中一个字符dp[i-1][j-1] + 1（不等时）
无操作字符相同，无需操作dp[i-1][j-1]（相等时）
// LC 72 编辑距离 - 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(dp[i-1][j-1],
                               Math.min(dp[i-1][j], dp[i][j-1]));
        }
    }
    return dp[m][n];
}

四、背包问题（重点难点）

背包问题是 DP 中最经典的一类，分为 0-1 背包（每件物品最多选一次）和完全背包（每件物品可以选无数次）。

4.1 0-1 背包

问题描述：有 n 件物品，背包容量为 W。每件物品重量 w[i]，价值 v[i]，每件只能选一次。求能装入的最大价值。

Mermaid 决策树（以 2 件物品为例）：

状态定义：dp[i][j] = 前 i 件物品，容量为 j 时的最大价值

转移方程：

  • 不选第 i 件：dp[i][j] = dp[i-1][j]
  • 选第 i 件（j >= w[i]）：dp[i][j] = dp[i-1][j-w[i]] + v[i]
  • 综合：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

以物品 {(w=1,v=2), (w=2,v=3), (w=3,v=4)}，容量 W=4 为例，逐行填充：

📊 DP 填充过程演示

初始化：第0行全为0（无物品时，任何容量价值为0）
容量0容量1容量2容量3容量4
无物品00000
物品1(w=1,v=2)
物品2(w=2,v=3)
物品3(w=3,v=4)
1 / 4

滚动数组优化（空间从 O(nW) → O(W)）：

// 0-1 背包完整实现 + 滚动数组优化
public int knapsack01(int W, int[] weights, int[] values) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < weights.length; i++) {
        // 关键：必须从右向左遍历，防止物品被重复选取
        for (int j = W; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

核心区别：0-1 背包滚动数组从右向左遍历；完全背包从左向右遍历。

4.2 完全背包 —— 零钱兑换（LC 322）

题目：给定硬币面值数组和总金额，求凑出金额的最少硬币数（每种硬币可以无限使用）。

状态定义：dp[j] = 凑出金额 j 的最少硬币数

转移方程：dp[j] = min(dp[j], dp[j - coin] + 1)

初始化：dp[0]=0（凑出金额0不需要硬币），其余=∞（不可达）
dp[0]dp[1]dp[2]dp[3]dp[4]dp[5]
最少硬币数0∞∞∞∞∞
1 / 4
// LC 322 零钱兑换 - 完全背包
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1); // 用 amount+1 代替 INF
    dp[0] = 0;
    for (int coin : coins) {
        // 完全背包：从左向右遍历
        for (int j = coin; j <= amount; j++) {
            dp[j] = Math.min(dp[j], dp[j - coin] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

// LC 518 零钱兑换 II（组合数）
public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1; // 凑出金额0有1种方法（什么都不选）
    for (int coin : coins) {
        for (int j = coin; j <= amount; j++) {
            dp[j] += dp[j - coin];
        }
    }
    return dp[amount];
}

五、区间 DP

区间 DP 的特点：dp 下标为区间左右端点，通常按区间长度从小到大填充（对角线方向）。

5.1 最长回文子序列（LC 516）

状态定义：dp[i][j] = 字符串 s[i..j] 的最长回文子序列长度

转移方程：

  • 若 s[i] == s[j]：dp[i][j] = dp[i+1][j-1] + 2
  • 否则：dp[i][j] = max(dp[i+1][j], dp[i][j-1])

对角线填充可视化（字符串 "bbbab"）：

填充顺序：先填对角线（长度1），再逐步扩展到更长的区间
长度1: dp[i][i] = 1 (单个字符自身就是回文)
长度2: 如 dp[0][1]: s[0]='b'==s[1]='b', dp[0][1]=2
...
最终 dp[0][4] = 4，最长回文子序列为 "bbbb"
// LC 516 最长回文子序列
public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    // 初始化：每个单字符都是长度1的回文
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    // 按区间长度从小到大填充（对角线方向）
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j))
                dp[i][j] = dp[i+1][j-1] + 2;
            else
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
        }
    }
    return dp[0][n-1];
}

5.2 戳气球（LC 312）—— 经典区间 DP

思路：逆向思考，枚举最后一个被戳破的气球 k，区间 [i, j] 的最大收益为：

dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])

// LC 312 戳气球
public int maxCoins(int[] nums) {
    int n = nums.length;
    // 在两端各加一个1作为哨兵
    int[] arr = new int[n + 2];
    arr[0] = arr[n + 1] = 1;
    for (int i = 1; i <= n; i++) arr[i] = nums[i - 1];
    int m = arr.length;
    int[][] dp = new int[m][m];
    // 枚举区间长度
    for (int len = 2; len < m; len++) {
        for (int i = 0; i < m - len; i++) {
            int j = i + len;
            for (int k = i + 1; k < j; k++) {
                dp[i][j] = Math.max(dp[i][j],
                    dp[i][k] + dp[k][j] + arr[i] * arr[k] * arr[j]);
            }
        }
    }
    return dp[0][m - 1];
}

六、树形 DP

6.1 打家劫舍 III（LC 337）

题目：二叉树版打家劫舍，相邻节点（父子）不能同时抢。

每个节点维护两个状态：

  • rob：抢当前节点时的最大收益
  • notRob：不抢当前节点时的最大收益
// LC 337 打家劫舍 III - 树形 DP
public int rob(TreeNode root) {
    int[] result = dfs(root);
    return Math.max(result[0], result[1]);
}

// 返回 [不抢当前节点的最大值, 抢当前节点的最大值]
private int[] dfs(TreeNode node) {
    if (node == null) return new int[]{0, 0};
    int[] left = dfs(node.left);
    int[] right = dfs(node.right);
    // 不抢当前节点：子节点可抢可不抢，取最大
    int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    // 抢当前节点：子节点均不能抢
    int rob = node.val + left[0] + right[0];
    return new int[]{notRob, rob};
}

七、经典模板总结

7.1 一维 DP 通用模板

// 一维 DP 通用框架
int[] dp = new int[n + 1];
// 初始化边界
dp[0] = ...; dp[1] = ...;
// 状态转移（从前往后）
for (int i = 2; i <= n; i++) {
    dp[i] = f(dp[i-1], dp[i-2], ...); // 根据题目填写转移方程
}
return dp[n];

7.2 二维 DP 通用模板

// 二维 DP 通用框架
int[][] dp = new int[m + 1][n + 1];
// 初始化边界（第0行/列）
for (int i = 0; i <= m; i++) dp[i][0] = ...;
for (int j = 0; j <= n; j++) dp[0][j] = ...;
// 状态转移（双层循环）
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
    }
}
return dp[m][n];

7.3 背包 DP 模板对比

// 0-1 背包（每件物品最多选一次）—— 从右向左
for (int i = 0; i < n; i++) {
    for (int j = W; j >= w[i]; j--) {  // 逆序！
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
    }
}

// 完全背包（每件物品可选无数次）—— 从左向右
for (int i = 0; i < n; i++) {
    for (int j = w[i]; j <= W; j++) {  // 正序！
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
    }
}

7.4 区间 DP 模板

// 区间 DP 通用框架（按区间长度从小到大）
int[][] dp = new int[n][n];
// 初始化长度为1的区间
for (int i = 0; i < n; i++) dp[i][i] = ...;
// 枚举区间长度
for (int len = 2; len <= n; len++) {
    for (int i = 0; i <= n - len; i++) {
        int j = i + len - 1;
        // 枚举分割点 k
        for (int k = i; k < j; k++) {
            dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k+1][j] + cost);
        }
    }
}
return dp[0][n-1];

7.5 树形 DP 模板

// 树形 DP 通用框架（后序遍历）
int[] dfs(TreeNode node) {
    if (node == null) return new int[]{0, 0}; // 边界
    int[] left = dfs(node.left);   // 递归左子树
    int[] right = dfs(node.right); // 递归右子树
    // 利用子树状态计算当前节点状态
    int state0 = f(left, right);       // 不选当前节点
    int state1 = g(left, right, node); // 选当前节点
    return new int[]{state0, state1};
}

八、DP 题型速查表

题型代表题目核心思路时间复杂度
斐波那契型LC 70 爬楼梯dp[i]=dp[i-1]+dp[i-2]O(n)
打劫型LC 198 打家劫舍dp[i]=max(dp[i-1], dp[i-2]+nums[i])O(n)
LISLC 300 最长递增子序列贪心+二分O(nlogn)
路径型LC 64 最小路径和dp[i][j]=min(上,左)+grid[i][j]O(mn)
LCSLC 1143 公共子序列字符相等+1，否则取maxO(mn)
编辑距离LC 72 编辑距离三种操作取minO(mn)
0-1背包背包问题逆序遍历容量O(nW)
完全背包LC 322 零钱兑换正序遍历容量O(nW)
区间DPLC 312 戳气球枚举最后一个操作O(n³)
树形DPLC 337 打家劫舍III后序遍历，子树状态上推O(n)

学习建议：DP 不是靠背题目，而是靠理解状态定义和转移逻辑。每做一道题，先不看代码，强迫自己用五步法推导一遍，再对照代码验证。坚持 30 道题，你会发现大部分 DP 题的本质都是换了皮的"老朋友"。

系统学习算法

想要系统地从零刷穿算法面试题？欢迎加入知识星球「代码精进之路」，内含：

  • 300+ LeetCode 高频题详解（含 DP 专项 50 题）
  • 按公司/难度分类的刷题路线图
  • 每周算法打卡 + 一对一答疑
  • 大厂面试真题复盘

扫码或搜索「代码精进之路」加入，一起高效备战算法面试！

编辑此页
最近更新:
贡献者: xiaozhangge