动态规划算法入门：从暴力递归到状态转移的完整思维指南

当你第一次尝试实现斐波那契数列时,可能会写出这样的递归代码:

public int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

这段代码看起来简洁优雅,但当 n 达到 50 时,程序会运行很长时间才能返回结果。问题出在哪里?重复计算。计算 fib(5) 时会调用 fib(3),计算 fib(4) 时又会再次调用 fib(3)。随着 n 增大,重复计算的次数呈指数级增长——时间复杂度高达 $O(2^n)$。

如果在计算 fib(3) 时把结果保存起来,下次需要时直接使用,就能避免重复计算。这正是动态规划的核心思想。

动态规划是什么

动态规划(Dynamic Programming,简称DP)是一种通过将复杂问题分解为更小的子问题,并存储子问题的解来避免重复计算的算法设计方法。

1953年,美国数学家 Richard Bellman 在研究多阶段决策过程优化问题时正式提出了动态规划的概念。他在自传中解释,“动态规划"这个名称其实是为了掩人耳目——当时他所在的兰德公司(RAND Corporation)对"数学研究"并不友好,所以他选择了一个听起来更像工程术语的名字。

动态规划的本质可以用一句话概括:用空间换时间。通过存储已经计算过的子问题的结果,将指数级的时间复杂度降低到多项式级别。

动态规划概念图

图片来源: GeeksforGeeks

三个核心特征

不是所有问题都适合用动态规划解决。一个问题能够使用动态规划,必须满足三个特征:

1. 最优子结构

最优子结构是指,一个问题的最优解包含其子问题的最优解。换句话说,如果我们要求解问题 P,可以把 P 分解为若干个子问题 P1, P2, …, Pk,那么 P 的最优解可以通过组合这些子问题的最优解得到。

以最短路径问题为例:从城市 A 到城市 C 的最短路径,如果经过城市 B,那么这条路径的 A→B 部分一定是从 A 到 B 的最短路径,B→C 部分一定是从 B 到 C 的最短路径。如果 A→B 的部分存在更短的路径,我们就可以用它替换原来的路径,从而得到更短的 A→C 路径——这与"最短路径"的定义矛盾。

2. 重叠子问题

重叠子问题是指在求解过程中,同一个子问题会被反复计算多次。这是动态规划与分治算法的主要区别。

分治算法(如归并排序)将问题分解为独立的子问题,每个子问题只需计算一次。而动态规划处理的子问题是重叠的——同一个子问题会在不同的递归分支中被多次遇到。

以斐波那契数列为例,计算 fib(5) 的递归树如下:

                fib(5)
              /        \
          fib(4)       fib(3)
         /    \        /    \
     fib(3)  fib(2)  fib(2)  fib(1)
     /   \
  fib(2) fib(1)

可以看到,fib(3) 被计算了 2 次,fib(2) 被计算了 3 次。这种重叠使得暴力递归效率极低。

3. 无后效性

无后效性是指,某个状态一旦确定,其后续的决策不会影响之前的状态。换句话说,“过去"不会因为"未来"而改变。

以爬楼梯问题为例:假设你站在第 i 级台阶上,下一步怎么走只取决于你当前在哪一级台阶,而不需要知道你是怎么到达这一级的。第 i 级台阶的状态(已经走了多少步)一旦确定,后续的决策就只与这个状态有关,与到达这个状态的路径无关。

无后效性是定义状态的关键前提。如果问题存在后效性,那么仅用当前状态就无法完整描述问题,需要额外记录历史信息。

两种实现方式

动态规划有两种主要的实现方式:自顶向下的记忆化搜索和自底向上的迭代填表。

自顶向下:记忆化搜索

记忆化搜索本质上是递归+缓存。从原始问题出发,递归地求解子问题,每次求解前先检查缓存中是否已有结果,若有则直接返回,避免重复计算。

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

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

时间复杂度:$O(n)$,每个子问题只计算一次。空间复杂度:$O(n)$,存储 memo 数组和递归栈。

自底向上:迭代填表

迭代填表从最小子问题开始,逐步计算更大的子问题,直到求得原始问题的解。通常使用一个数组或表格存储中间结果。

public int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

时间复杂度:$O(n)$ 空间复杂度:$O(n)$,可以优化到 $O(1)$

两种方式各有优劣。记忆化搜索更直观,容易从递归解法转换而来,但存在递归栈开销。迭代填表更高效,且便于空间优化,但需要正确确定计算顺序。

动态规划解题框架

解决动态规划问题,可以遵循以下步骤:

第一步:定义状态

状态是对子问题的数学描述。需要思考:要解决当前问题,需要知道哪些信息?通常用 dp[i] 或 dp[i][j] 等数组表示状态。

第二步:推导状态转移方程

状态转移方程描述了状态之间的递推关系。需要思考:从已知状态如何推导出新的状态?这是动态规划的核心。

第三步:确定初始条件和边界

初始条件是最小子问题的解,边界条件处理特殊情况。

第四步:确定计算顺序

根据状态转移方程,确定是从小到大计算还是从大到小计算。基本原则是:计算某个状态时,它依赖的所有状态必须已经计算完成。

第五步:实现并优化

写出代码,然后考虑是否可以优化空间复杂度。

LeetCode 经典题目解析

下面通过 LeetCode 上的经典题目,深入理解动态规划的应用。

一、线性动态规划

1. 爬楼梯(LeetCode 70)

问题描述:假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶?

思路分析:

要到达第 n 级台阶,最后一步只有两种可能:从第 n-1 级迈一步,或从第 n-2 级迈两步。因此,到达第 n 级的方法数等于到达第 n-1 级和第 n-2 级的方法数之和。

状态定义:dp[i] 表示到达第 i 级台阶的方法数。

状态转移方程:

$$dp[i] = dp[i-1] + dp[i-2]$$

初始条件:dp[1] = 1, dp[2] = 2

Java 实现:

class Solution {
    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];
    }
}

空间优化版本:

由于状态转移只依赖前两个状态,可以用两个变量代替整个数组:

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        
        int prev2 = 1, prev1 = 2;
        for (int i = 3; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
}

时间复杂度:$O(n)$ 空间复杂度:$O(1)$

2. 打家劫舍(LeetCode 198)

问题描述:你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组,计算你不触动警报装置的情况下,一夜之内能够偷窃到的最高金额。

思路分析:

对于第 i 间房子,有两种选择:偷或不偷。

如果偷第 i 间,则不能偷第 i-1 间,最大金额为:偷前 i-2 间房子的最大金额 + 第 i 间房子的金额
如果不偷第 i 间,则最大金额为:偷前 i-1 间房子的最大金额

选择两者中的较大值。

状态定义:dp[i] 表示偷窃前 i 间房子能获得的最大金额。

状态转移方程:

$$dp[i] = \max(dp[i-1], dp[i-2] + nums[i-1])$$

初始条件:dp[0] = 0, dp[1] = nums[0]

Java 实现:

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        
        return dp[n];
    }
}

空间优化版本:

class Solution {
    public int rob(int[] nums) {
        int prev2 = 0, prev1 = 0;
        
        for (int num : nums) {
            int curr = Math.max(prev1, prev2 + num);
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
}

时间复杂度:$O(n)$ 空间复杂度:$O(1)$

二、背包问题

3. 零钱兑换(LeetCode 322)

问题描述:给定不同面额的硬币 coins 和一个总金额 amount,编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

思路分析:

这是一个完全背包问题(每种硬币可以使用无限次)。对于金额 amount,可以尝试使用每种硬币:

如果使用面值为 coin 的硬币,剩余金额为 amount - coin
问题转化为:凑成金额 amount - coin 需要的最少硬币数 + 1

状态定义:dp[i] 表示凑成金额 i 需要的最少硬币数。

状态转移方程:

$$dp[i] = \min_{coin \in coins}(dp[i - coin] + 1)$$

初始条件:dp[0] = 0,其他位置初始化为 amount + 1(一个不可能达到的大值,用于判断无解)

Java 实现:

class Solution {
    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 (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

时间复杂度:$O(amount \times n)$,n 为硬币种类数空间复杂度:$O(amount)$

三、字符串动态规划

4. 单词拆分(LeetCode 139)

问题描述:给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

思路分析:

定义 dp[i] 表示字符串 s 的前 i 个字符(s[0..i-1])能否被拆分。对于位置 i,尝试所有可能的分割点 j:

如果 dp[j] 为 true 且 s[j..i-1] 在字典中,则 dp[i] 为 true

状态定义:dp[i] 表示前 i 个字符能否被成功拆分。

状态转移方程:

$$dp[i] = \bigvee_{j=0}^{i-1} (dp[j] \land s[j..i-1] \in wordDict)$$

初始条件:dp[0] = true(空字符串默认可以拆分)

Java 实现:

class Solution {
    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++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[n];
    }
}

时间复杂度:$O(n^2)$,n 为字符串长度空间复杂度:$O(n)$

5. 最长递增子序列(LeetCode 300)

问题描述:给定一个无序的整数数组,找到其中最长上升子序列的长度。

思路分析:

定义 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。对于每个元素 nums[i],遍历它前面的所有元素 nums[j]:

如果 nums[j] < nums[i],则 nums[i] 可以接在以 nums[j] 结尾的递增子序列后面,长度为 dp[j] + 1

状态定义:dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。

状态转移方程:

$$dp[i] = \max_{j < i, nums[j] < nums[i]}(dp[j] + 1)$$

初始条件:dp[i] = 1(每个元素自身构成长度为 1 的子序列)

Java 实现:

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxLen = 1;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        
        return maxLen;
    }
}

时间复杂度:$O(n^2)$ 空间复杂度:$O(n)$

进阶优化:可以使用二分查找将时间复杂度优化到 $O(n \log n)$,但需要更复杂的数据结构。

四、二维动态规划

6. 最长公共子序列(LeetCode 1143)

问题描述:给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。

思路分析:

定义 dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列长度。

对于字符 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])

状态定义:dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列长度。

状态转移方程:

$$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } text1[i-1] = text2[j-1] \\ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise} \end{cases}$$

初始条件:dp[0][j] = 0, dp[i][0] = 0

Java 实现:

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];
    }
}

时间复杂度:$O(m \times n)$ 空间复杂度:$O(m \times n)$,可以优化到 $O(\min(m, n))$

7. 编辑距离(LeetCode 72)

问题描述:给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作:插入一个字符、删除一个字符、替换一个字符。

思路分析:

定义 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数。

对于字符 word1[i-1] 和 word2[j-1]:

如果相等,不需要操作,dp[i][j] = dp[i-1][j-1]
如果不等,有三种操作:
- 插入:dp[i][j-1] + 1
- 删除:dp[i-1][j] + 1
- 替换:dp[i-1][j-1] + 1

状态转移方程:

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

初始条件:dp[i][0] = i(删除 i 个字符),dp[0][j] = j(插入 j 个字符)

Java 实现:

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(dp[i - 1][j - 1], 
                              Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }
        
        return dp[m][n];
    }
}

时间复杂度:$O(m \times n)$ 空间复杂度:$O(m \times n)$

五、股票买卖系列

股票买卖问题有一个通用的状态设计框架。定义两个状态数组:

dp[i][0]:第 i 天结束时,不持有股票的最大利润
dp[i][1]:第 i 天结束时,持有股票的最大利润

8. 买卖股票的最佳时机(LeetCode 121)

问题描述:给定一个数组 prices,它的第 i 个元素 prices[i] 是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易(即买入和卖出一只股票),设计一个算法来计算你所能获取的最大利润。

Java 实现:

class Solution {
    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)$

空间优化技巧

动态规划的一个常见优化方向是降低空间复杂度。当状态转移方程只依赖有限个前驱状态时,可以使用滚动数组或变量替换整个 DP 数组。

以爬楼梯问题为例,状态转移方程为:

$$dp[i] = dp[i-1] + dp[i-2]$$

计算 dp[i] 只需要 dp[i-1] 和 dp[i-2],不需要保存整个数组。可以用两个变量代替:

int prev2 = 1, prev1 = 2;
for (int i = 3; i <= n; i++) {
    int curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
}

这种优化将空间复杂度从 $O(n)$ 降低到 $O(1)$。

对于二维 DP,如果状态转移只依赖上一行或上一列,同样可以优化。例如,最长公共子序列问题可以优化到 $O(\min(m, n))$ 的空间复杂度。

常见陷阱

1. 初始条件错误

初始条件是最小子问题的解,必须正确处理边界情况。例如,空字符串、空数组、索引为 0 的情况等。

2. 状态定义不清晰

状态定义必须准确反映子问题的含义。模糊的状态定义会导致错误的状态转移方程。建议用一句话清晰地描述状态的含义。

3. 计算顺序错误

计算某个状态时,它依赖的所有状态必须已经计算完成。自底向上的迭代需要正确确定计算顺序。

4. 空间优化时的覆盖问题

使用滚动数组时,要确保不会覆盖还需要使用的状态。通常需要临时变量保存中间结果。

5. 忽略无解情况

有些问题可能无解,需要特殊处理。例如,零钱兑换问题中,如果无法凑出目标金额,应该返回 -1。

实际应用

动态规划在实际工程中有广泛的应用:

版本控制系统的 diff 算法:Git 的 git diff 命令使用最长公共子序列(LCS)算法来比较两个文件版本之间的差异。通过 LCS 找出公共部分,其余部分就是修改的内容。

文本编辑器:拼写检查、智能补全等功能中,计算两个字符串的相似度(如编辑距离)是核心操作。

路径规划:地图导航应用中的最短路径算法(如 Bellman-Ford、Floyd-Warshall)基于动态规划。

图像处理:图像缩放、图像分割等问题中,动态规划用于寻找最优分割线或最优缩放策略。

自然语言处理:分词、词性标注、句法分析等任务中,动态规划用于寻找最优序列。

总结

动态规划是一种强大的算法设计方法,核心思想是用空间换时间,通过存储子问题的解来避免重复计算。掌握动态规划需要理解三个核心特征:最优子结构、重叠子问题、无后效性,以及两种实现方式:记忆化搜索和迭代填表。

解决动态规划问题的关键在于正确定义状态和推导状态转移方程。从斐波那契数列到爬楼梯,从背包问题到字符串匹配,动态规划的应用场景非常广泛。通过大量练习 LeetCode 题目,可以逐步培养识别动态规划问题和设计状态的能力。

参考资料

GeeksforGeeks. Introduction to Dynamic Programming. https://www.geeksforgeeks.org/dynamic-programming/
LeetCode. Dynamic Programming Problem List. https://leetcode.com/problem-list/dynamic-programming/
Labuladong. Dynamic Programming Patterns. https://labuladong.online/
Cormen, T. H., et al. Introduction to Algorithms, 3rd Edition, MIT Press, 2009.
Bellman, R. Dynamic Programming, Princeton University Press, 1957.
VisuAlgo. Recursion Tree and DAG Visualization. https://visualgo.net/en/recursion

动态规划是什么#

三个核心特征#

1. 最优子结构#

2. 重叠子问题#

3. 无后效性#

两种实现方式#

自顶向下:记忆化搜索#

自底向上:迭代填表#

动态规划解题框架#

LeetCode 经典题目解析#

一、线性动态规划#

1. 爬楼梯(LeetCode 70)#

2. 打家劫舍(LeetCode 198)#

二、背包问题#

3. 零钱兑换(LeetCode 322)#

三、字符串动态规划#

4. 单词拆分(LeetCode 139)#

5. 最长递增子序列(LeetCode 300)#

四、二维动态规划#

6. 最长公共子序列(LeetCode 1143)#

7. 编辑距离(LeetCode 72)#

五、股票买卖系列#

8. 买卖股票的最佳时机(LeetCode 121)#

空间优化技巧#

常见陷阱#

实际应用#

总结#

参考资料#

更多精彩内容

背包问题为何成为动态规划的基石从01背包到完全背包的完整LeetCode通关指南

最长公共子序列为何能解决十几类LeetCode问题从字符串相似度到DNA比对的动态规划精髓

树形动态规划：为什么一棵树的答案要从叶子开始算

回溯算法:从决策树到剪枝优化的完整LeetCode通关指南

扫描线算法如何将二维问题降维成一维从天际线到矩形面积的LeetCode完整通关指南

动态规划是什么

三个核心特征

1. 最优子结构

2. 重叠子问题

3. 无后效性

两种实现方式

自顶向下:记忆化搜索

自底向上:迭代填表

动态规划解题框架

LeetCode 经典题目解析

一、线性动态规划

1. 爬楼梯(LeetCode 70)

2. 打家劫舍(LeetCode 198)

二、背包问题

3. 零钱兑换(LeetCode 322)

三、字符串动态规划

4. 单词拆分(LeetCode 139)

5. 最长递增子序列(LeetCode 300)

四、二维动态规划

6. 最长公共子序列(LeetCode 1143)

7. 编辑距离(LeetCode 72)

五、股票买卖系列

8. 买卖股票的最佳时机(LeetCode 121)

空间优化技巧

常见陷阱

实际应用

总结

参考资料