Skip to content
C++ 编程指南

动态规划

枚举、模拟、贪心、递归、二分、动态规划、图论等经典算法。

Updated View as Markdown

什么是动态规划

来自维基百科的定义：动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

也就是说，动态规划是一种用来解决一类最优化问题的算法思想和策略，并不是一种具体的算法。但这种算法思想非常强大且应用非常广泛，也是各类算法竞赛里的常客，所以大家一定要好好掌握。

再看 Fibonacci 数列

再来看看经典的 Fibonacci 数列问题：给一个正整数 n，寻找 Fibonacci 数列的第 n 项数字是多少？

斐波那契数以递归的方法来定义，其数学表达如下所示：

\begin{cases} & F_0=0 \\ & F_1=1 \\ & F_n=F_{n-1} + F_{n-2}\end{cases}

用文字来描述，就是斐波那契数列是从 0 和 1 开始，之后的斐波那契数是由之前的两数相加而得。

从第 1 项开始，斐波那契数列前几项依次是：

0, 1, 1, 2, 3, 5, 8, 13, 21,...

需要注意的是，斐波那契数列中，0 是第零项，而不是第一项

我们之前通常是用递归去完成的，这也很自然，毕竟斐波那契数列本身的定义就是一种递归形式。

代码如下：

#include <bits/stdc++.h>
using namespace std;

int fib(int n) {
	if (n == 0 || n == 1) return n;
	else return fib(n - 1) + fib(n - 2);
}

int main() {
  int n;
  cin >> n;
  
  cout << fib(n);
  return 0;
}

递归的方式很好理解，实现也非常简单。以 fib(4) 为例：

  • 想求 fib(4)，你需要先求 fib(3) 和 fib(2)。
  • 想求 fib(3)，你需要先求 fib(2) 和 fib(1)。
  • 想求 fib(2)，你需要先求 fib(1) 和 fib(0)。

一直往下求，直到已知的 fib(0) 和 fib(1) 。

大家发现问题了吗？为了计算 fib(4) ，我们计算了 fib(3) 和 fib(2)，在计算 fib(3) 时，又计算了一次 fib(2)，实际上，由于每次调用 fib() 都会产生两次额外的调用，如果 fib(n) 中的 n 稍大一点，就会产生很多重复的计算，这种重复计算会变得极其浪费时间，n 越大，程序会越慢，可能会慢到无法接受。

// 朴素递归计算斐波那契数 (效率很低)
int fib(int n) {
	if (n <= 1) {
		return n;
	}
	// 这里会重复计算很多次
	return fib(n - 1) + fib(n - 2);
}

如何改进这个问题呢？直观能想到的是把每次求出的 fib(n) 结果保存下来，如果下次需要再用到，直接拿出来用就是，而不是重新再算一遍，省时又省力。

按照这个思路改进后的代码如下：

#include <bits/stdc++.h>
using namespace std;

int dp[100]; // 假设我们最多求 fibonacci 数列第 100 项

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

int main() {
  int n;
  cin >> n;
  
  cout << fib(n);
  return 0;
}

通过数组来存放每次计算的结果。经过改进后，由于每个 fib() 只计算一次，算法的时间复杂度从 O(2^n) 降为 O(n) 。

刚刚这种解决问题的方式就是一种动态规划的算法思想，通过缓存子问题结果来避免重复计算。

动态规划的核心思想

动态规划不是一个具体的算法，而是一种解决问题的思维方式。它通常用来解决那些具有重叠子问题和最优子结构特性的问题。

  • 重叠子问题 (Overlapping Subproblems)： 就像上面斐波那契的例子，一个大问题的解决依赖于一些小问题，而这些小问题又会被反复需要。
  • 最优子结构 (Optimal Substructure)： 一个大问题的最优解，可以由它的小问题的最优解组合而成。比如，你要找从 A 到 Z 的最短路径，如果你找到了中间点 M，那么从 A 到 M 的那段路，一定也得是 A 到 M 的最短路径，否则整体就不是最短了。

动态规划的精髓在于：

  1. 拆分问题： 把一个复杂的大问题，拆解成一堆规模更小、更容易解决的子问题。
  2. 记住结果： 把每个子问题的解存储起来（通常用数组或类似的数据结构），避免重复计算。
  3. 组合答案： 利用子问题的解，按照一定的顺序（或者递推关系），最终构造出大问题的解。

动态规划的关键要素

要用动态规划解决一个问题，我们通常需要明确以下几个关键点：

状态

  • 是什么？ 状态是用来描述一个子问题的 独特标识。它需要包含所有必要的信息，以便能够区分不同的子问题，并且能够从这个状态推导出下一步。
  • 怎么找？ 思考一下，在解决问题的过程中，哪些变量在变化？哪些信息是区分不同子问题的关键？
  • 例子：
    • 在斐波那契问题中，子问题就是求 fib(k)，所以状态就是这个 k。我们通常用 dp[k] 来表示 fib(k) 的值。
    • 假设我们要在一个网格里从左上角走到右下角，只能向下或向右走。子问题可能是“到达格子 (i, j) 有多少种方法？” 那么状态就是 (i, j)。我们通常用 dp[i][j] 来表示到达格子 (i, j) 的方法数。

状态转移方程

  • 是什么？ 这是动态规划的 核心！它描述了 不同状态之间的关系，也就是如何从一个或多个 已知的子问题的解（较小规模的状态）推导出 当前子问题的解（较大规模的状态）。
  • 怎么找？ 思考一下，对于当前状态 dp[i] (或 dp[i][j])，它的解可以由哪些 更小规模 的状态 dp[k] (其中 k < i) 或 dp[x][y](其中 x <= i, y <= j 且 (x,y) != (i,j)) 组合或计算得到？
  • 例子：
    • 斐波那契问题：dp[k] 的值取决于 dp[k-1] 和 dp[k-2]。状态转移方程就是：dp[k] = dp[k-1] + dp[k-2]。
    • 网格路径问题：要到达 (i, j)，只能从上面 (i-1, j) 或者左边 (i, j-1) 过来。所以状态转移方程是：dp[i][j] = dp[i-1][j] + dp[i][j-1]。

边界条件/初始状态

  • 是什么？ 状态转移方程定义了状态之间的递推关系，但这个递推不能无限进行下去，需要有 起点。边界条件就是那些 最小的、无法再拆分的子问题 的解，它们的值是已知的或者可以直接确定的。
  • 怎么找？ 思考一下，状态转移方程在什么情况下会失效？最小的子问题是什么？
  • 例子：
    • 斐波那契问题：dp[0] = 0, dp[1] = 1。这是递推的起点。
    • 网格路径问题：通常左上角 dp[0][0] 是起点。如果只能向下或向右，那么第一行 dp[0][j] 和第一列 dp[i][0] 的走法通常只有一种（除非有障碍物）。例如，dp[0][0] = 1，dp[i][0] = 1 (只能一路向下)，dp[0][j] = 1 (只能一路向右)。

计算顺序

  • 是什么？ 动态规划要求，在计算某个状态 dp[i] 时，它所依赖的那些状态 dp[k] (k < i) 必须 已经被计算出来。因此，我们需要确定一个合适的计算顺序。
  • 两种常见方式：
    • 自底向上 (Bottom-Up): 从最小的子问题（边界条件）开始，按照状态从小到大的顺序，依次计算并填充 DP 表（通常是数组），直到计算出我们最终需要的大问题的解。也被称为制表法（Tabulation）。
    • 自顶向下 (Top-Down): 从大问题开始，使用递归函数来求解。但是，在函数入口处检查这个状态是否已经计算过（查表）。如果计算过，直接返回存储的结果；如果没有，就递归计算它所依赖的子问题，然后将计算结果存入表中，再返回。这种方式更符合人类的递归思考习惯，但有递归开销。也被称为备忘录法（Memoization）。

动态规划的实现方法

上面讲到，动态规划问题求解通常有两种实现方式，一种自顶向下（Top-Down），一种自底向上（Bottom-Up）。

下面我们分别来看看，仍然以 fib(n) 为例。

自顶向下 DP

前面我们经过改进后求 Fibnacci 数列第 n 项的递归方法就是用的自顶而下的 DP 求解。

自顶向下 DP 一般是通过改进递归来实现的，避免重复计算相同子问题的一种方法就是缓存这些子问题的结果（维护一个已计算的值表）。

  • 如果缓存中包含当前要求的某个输入的结果，则直接从缓存中返回该值。
  • 否则，计算并将结果存入缓存，当下次需要解决同样的子问题时，就不需要再计算，直接从缓存拿结果。

这种通过缓存子问题结果的方法也被称为备忘录（Memoization），通过备忘录可以消除许多递归调用。

通过缓存子问题结果，我们的算法时间复杂度降到 O(n)；另外，要求 fib(n)，我们需要计算 fib(n-1) 和 fib(n-2)，一直到 fib(1) 和 fib(0)，这意味着我们的空间复杂度也为 O(n) 。

【补充优化后加注释的代码】

  • 优点： 写起来比较自然，接近递归的思路。只计算了实际需要的状态。
  • 缺点： 有递归函数调用的开销。如果递归深度太深，可能导致栈溢出。

自底向上

如果解决一个问题的办法是先解 「较小」的子问题，再逐步解决更大的问题，直到解决最终问题，这种方法就被称为自底向上的方法，自底向上一般是通过迭代来解决，

#include <iostream>
using namespace std;

const int MAXN = 100;
int f[MAXN];

void fib() {
    // 初始化边界条件
    f[0] = 0;
    f[1] = 1;

    // 状态转移方程
    for (int i = 2; i < MAXN; ++i) {
        f[i] = f[i - 1] + f[i - 2];
    }

    // 输出结果
    for (int i = 0; i < MAXN; ++i) {
        cout << f[i] << " ";
    }
}

int main() {
    fib();
    return 0;
}

以上代码中，f[i] 表示斐波那契数列的第 i 项。我们使用动态规划的方法，通过状态转移方程和边界条件，避免了重复计算，从而高效地求解了斐波那契数列问题。

使用 “自底而上” 的方法，只需要保留当前计算所需的子问题的解，而在“自顶而下“的方法中，需要保存所有子问题的解。

对于求 Fibonacci 数例第 n 项这个示例来说，”自底而上“只需要保留前两个数字的值，因此空间复杂度从 O(n) 降低到 O(1)。

  • 优点： 没有递归开销，效率通常更高。实现是迭代式的，不容易栈溢出。
  • 缺点： 需要明确计算顺序，有时可能计算了一些最终用不到的状态（但通常影响不大）。

空间优化（对于斐波那契）

我们再来看看是否还可以优化？

我们注意到，在整个计算的过程中，计算 dp[i] 其实只需要 dp[i-1] 和 dp[i-2] 的值。我们并不需要保存整个 dp 数组。可以用两个变量滚动计算。

按照这个思路，在计算过程中，我们只需要保留三个值，当前值和前两项的值，其它不需要的值都可以丢弃。

经过再次改进的代码如下：

#include <bits/stdc++.h>
using namespace std;

// 空间优化后的 fib() 方法
int fib(int n) {
  if (n == 0 || n == 1) return n;
  
  int prev1 = 1; // 相当于 dp[i - 1]
  int prev2 = 0; // 相当于 dp[i - 2]
  int current = 0; // 相当于 dp[i]
  
	for (int i = 2; i <= n; i++) {
	  current = prev1 + prev2;
	  // 更新，为下一次迭代做准备
	  prev2 = prev1;
	  prev1 = current;
	}
	return current;
}

int main() {
  int n;
  cin >> n;

  cout << fib(n);
  return 0;
}

优化后版本，时间复杂度仍然是 O(n)，但空间复杂度是恒定的，不再随输入的大小而增大，因此空间复杂度为 O(1)，相比我们最初的普通递归版本，效率已大大提升！

注：这种优化技巧在很多 DP 问题中都可能用到，当计算当前状态只需要前面少数几个状态时，可以大大减少空间复杂度。

动态规划求解基本步骤

当遇到一个动态规划的问题时，可以尝试遵循以下步骤来进行求解：

  1. 定义状态：明确子问题的状态，也就是用什么来表示一个子问题，即 dp[i] 或 dp[i][j] 代表什么含义。这是关键的一步，状态定义得好，后面的状态转移议程就比较好找。
  2. 定义状态转移方程：找到状态之间的关系，即当前状态是如何由之前的状态推导出来的。即 dp[i] 或 dp[i][j] 是如何由前面的状态推导出来的。这是 DP 的核心逻辑。
  3. 确定边界条件：找到最小的子问题，它的解是什么？确定状态转移方程的初始状态。这是递推的起点。
  4. 选择实现方式：确定状态的计算顺序，以避免重复计算。决定是用自顶而下，还是自底而上来实现。通常自底而上更常用，也更容易进行空间优化。

在求解动态规划相关的问题时，如何识别和定义状态和状态转移方程是核心，也是最难的部分。

动态规划使用场景

动态规划的应用非常广泛，是一些经典算法问题的基础：

  • 背包问题： 在容量有限的背包里装物品，如何使得总价值最大？（0/1背包、完全背包、多重背包）
  • 最长公共子序列 (LCS)： 找到两个字符串共有的、最长的子序列。
  • 最长递增子序列 (LIS)： 在一个序列中找到最长的、单调递增的子序列。
  • 编辑距离： 计算将一个字符串转换成另一个字符串所需的最少操作次数（插入、删除、替换）。
  • 路径问题： 网格中的最短路径、不同路径计数等。
  • 区间 DP： 在一个区间上进行合并、划分等操作求最优解。
  • 树形 DP： 在树结构上进行动态规划。
  • 状态压缩 DP： 当状态的某个维度很小（比如小于 20）时，可以用二进制数来表示状态。

简单一维动态规划

这里的“一维”指的就是我们用来定义子问题状态的关键变量只有一个。

回顾一下前面举的求斐波那契数列第 n 项的例子，子问题状态就是 dp[i]，要解决关于第 i 项的问题，只需要知道前 dp[i-1] 项和 dp[i-2] 项，这里的 i 就是那个唯的关键变量，它代表了问题的规模，求斐波那契数列第 n 项这个问题就是一个一维动态规划问题，一维动态规划问题通常也简称：一维 DP。

简单来说，一维 DP 就是用一个一维数组 dp[i] 来记录状态，并且 dp[i] 的计算通常只依赖于 dp[j] (其中 j < i) 的值。就像多米诺骨牌一样，dp[0] (或 dp[1]) 是第一块牌，然后你可以用它推倒 dp[1]，再用 dp[1] 推倒 dp[2]… 一直推到你想要的最终答案 dp[n]。

一维 DP 通常用于解决与序列、路径、计数、最大/最小相关的问题，且问题的状态可以被一个单一的维度（如下标、长度、数值等）刻画。

示例：最大子数组和

问题描述

给一定一个整数数组 a，找到一具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

例如，对于一组 n 个整数，n = 7，这 7 个整数为 -2 13 12 9 14 -10 2，其具有最大和的连续子数组为 13 12 9 14，最大和为 48。

样例输入数据

7
-2 13 12 9 14 -10 2

样例输出数据

48

题目分析

状态定义：dp[i] 表示以数组元素 a[i] 结尾的连续子数组的最大和。

状态转移方程：对于 dp[i]，以 a[i] 结尾的最大和子数组只有两种可能，dp[i] 要么是 a[i]，要么是 dp[i-1] + a[i]，取两者中的较大值，用代码表示出来就是：dp[i] = max(a[i], dp[i-1] + a[i]) (对于 i >= 1)

初始状态：dp[0] = a[0]，表示第一个元素结尾的最大和就是它本身。

最后我们只需要找到 dp[i] 中的最大值即可。

代码实现

#include <bits/stdc++.h>
using namespace std;

int n, mx, q[110], dp[110];

int main() {
  cin >> n;

  for (int i = 0; i < n; i++) cin >> q[i];

  dp[0] = q[0];
  mx = dp[0];

  for (int i = 1; i < n; i++) {
    dp[i] = max(dp[i - 1] + q[i], q[i]); // 两种可能中的较大值
    mx = max(dp[i], mx); // 保留最大值
  }

  cout << mx << endl;

  return 0;
}

代码实现（空间优化版本）

同样的，你会发现，dp[i] 仅仅依赖 dp[i - 1] ，在这种情况下，我们其实不需要存储整个 dp 数组，与前面的斐波那契数列空间优化一样，用几个变量来滚动保存所需的状态即可，这样可以将空间复杂度从 O(n) 优化到 O(1)。

优化的参考代码如下：

#include <bits/stdc++.h>
using namespace std;

int n, curr_mx, mx, q[110];

int main() {
  cin >> n;

  for (int i = 0; i < n; i++) cin >> q[i];

  curr_mx = q[0]; // 替代了 dp[i]
  mx = q[0];

  for (int i = 1; i < n; i++) {
    curr_mx= max(curr_mx + q[i], q[i]); // 两种可能中的较大值
    mx = max(curr_mx, mx); // 保留最大值
  }

  cout << mx << endl;

  return 0;
}

示例：最长递增子序列 (LIS)

什么是最长递增子序列

首先我们要明白什么是子序列，给定一个序列（比如一个数组 q[]），它的子序列是通过删除原序列中的零个或多个元素，但保持剩下元素的相对顺序不变得到的序列。

例如，对于序列 `q = [3, 1, 4, 1, 5, 9]

  • [1, 4, 5, 9] 是一个子序列（删除了 3 和第一个 1）
  • [3, 4, 9] 是一个子序列 (删除了 1、 1和 5)。
  • [1, 3, 4] 不是 子序列，因为 1 和 3 的相对顺序改变了。
  • [1, 5, 6] 不是 子序列，原序列中没有数字 6

“递增”指的是子序列中的元素从左到右是 严格增大 的，需要注意的是，有时题目中要求的是非递减子序列，即允许相邻元素是相等的。我们这里讨论的是严格递增的子序列。

综合起来，最长递增子序列（Longest Increasing Subsequence, LIS）就是在一个给定的序列中，找到一个最长的、且元素严格递增的子序列。

例如，对于序列 q = [3, 1, 4, 1, 5, 9, 2, 6]

  • [1, 4, 5, 9] 是一个递增子序列，长度为 4。
  • [1, 4, 5, 6] 是一个递增子序列，长度为 4。
  • [3, 4, 5, 9] 是一个递增子序列，长度为 4。
  • [3, 4, 5, 6] 是一个递增子序列，长度为 4。
  • [1, 2, 6] 是一个递增子序列，长度为 3。
  • [1, 1, 5, 9] 不是递增子序列 (因为有两个 1)。
  • [3, 1] 不是递增子序列。

在这个例子中，最长的递增子序列长度是 4。可能有多个 LIS，但它们的长度都是一样的。我们通常只关心这个 最大长度。

LIS 问题也是算法面试和编程竞赛中的常见题型。显然，你可以通过枚举法，把所有的子序列全找出来，然后求出每个子序列的长度，再找出长度的最大值，但我们这里主要讨论的是效率更高的动态规划解法。

动态规划求解

状态定义

第一步，需要找到合适的状态定义。

我们要求整个序列的 LIS 长度，能不能把它分解成子问题？

对于含有 n 个元素的序列 q[n] 要求其最大递增子序列的长度，如果我们知道以 q[i] 这个元素为结尾的最长递增子序列长度是多少，就只需要推导出以 q[i+1] 为结尾的最长递增子序列长度是多少就行了。

状态定义：dp[i] 表示在原序列 q 中，以元素 q[i] 为结尾的最长递增子序列的长度。

注意：这里定义的 dp[i] 不是前 i 个元素的 LIS 长度，而是 q[i] 这个特定元素为结尾的 LIS 长度。

状态转移方程

仍然以序列 q = [3, 1, 4, 1, 5, 9, 2, 6] 为例。

先看最简单的情况，dp[1] 就表示以 q[1] 这个元素为结尾的 LIS 长度，显然：

  • dp[1] = 1，表示以 q[1]，也就是元素 3 为结尾的 LIS 长度，因为只有一个元素，长度当然就是 1

再看 dp[2]

【补充内容】

初始状态/边界条件

对于每一个 q[i]，以它为结尾的 LIS 最差也就是它一个元素，因此初始值为 1。

计算顺序

dp[i] 的计算依赖于 dp[j] (j < i)。所以，我们需要按照 i 从 0 到 n-1 的顺序来计算 dp 数组。

我们计算出的 dp[i] 是以 a[i] 结尾的 LIS 长度。但整个序列的 LIS 不一定是以最后一个元素 a[n-1] 结尾的，它可能以任何一个 a[i]结尾。

所以，最终的答案是 所有 dp[i] (0 <= i < n) 中的最大值。

参考代码

#include <bits/stdc++.h>
using namespace std;

int n, mx, q[10010], dp[10010];

int main() {
  cin >> n;

  for (int i = 1; i <= n; i++) {
    cin >> q[i];
    dp[i] = 1; // 全部初始化为 1
  }

  mx = 1;

  for (int i = 2; i <= n; i++) {
    for (int j = 1; j < i; j++) {
      if (q[j] < q[i]) {
        dp[i] = max(dp[j] + 1, dp[i]);
      }
    }
    mx = max(dp[i], mx);
  }

  cout << mx << endl;
  return 0;
}

复杂度分析

  • 时间复杂度： 我们有一个外层循环 i 从 0 到 n-1，内部有一个嵌套循环 j 从 0 到 i-1。主要的计算在内层循环的比较和更新。总的计算次数大约是 1 + 2 + ... + (n-1)，这是 O(n^2) 级别的。
  • 空间复杂度： 我们需要一个 dp 数组来存储中间结果，大小为 n。所以空间复杂度是 O(n)。

动态规划求解（优化版）

虽然 O(n^2) 的 DP 方法很直观，但在 n 比较大（例如 n=10^5）时会超时。存在一种更优化的方法，可以将时间复杂度降到 O(n log n)。

这个方法的核心思想有点不同，它不再直接计算 dp[i]（以 a[i] 结尾的 LIS 长度），而是维护一个 “最优”结构。

核心思想： 维护一个数组 tails (或者叫 min_end)，其中 tails[k] 存储的是 所有长度为 k+1 的递增子序列中，结尾元素的最小值。

为什么这个有用？ 因为如果我们要构成一个更长的递增子序列，我们肯定希望它的结尾元素尽可能小，这样后面才更有可能接上新的元素。

算法流程：

  1. 初始化一个空数组 tails。
  2. 遍历原序列 a 中的每个元素 num：
    • 二分查找： 在 tails 数组中查找第一个 大于或等于 num 的元素的位置 idx。
      • 可以使用 C++ 的 lower_bound 函数。
    • 情况一： 如果 tails 中所有元素都比 num 小（即 lower_bound 返回 tails.end()），说明 num 可以扩展目前最长的递增子序列，使其长度加 1。将 num 添加到 tails 的末尾。
    • 情况二： 如果找到了这样一个位置 idx，说明 num 可以替换掉 tails[idx]。为什么？因为 num <= tails[idx]，用 num作为长度为 idx+1 的递增子序列的结尾，比用原来的 tails[idx] 作为结尾 更优（或者一样优，但值更小），因为它为后续元素提供了更多可能性。所以，更新 tails[idx] = num。
  3. 遍历结束后，tails 数组的 长度 就是原序列 LIS 的长度。

参考代码

// 1893 - 最长上升子序列LIS（2）
#include <bits/stdc++.h>
using namespace std;

int n, l, r, len, dp[100010], q[100010];

int main() {
  scanf("%d", &n);

  for (int i = 1; i <= n; i++) scanf("%d", &q[i]);

  dp[1] = q[1];

  len = 1;
  for (int i = 2; i <= n; i++) {
    if (q[i] > dp[len]) {
      len++;
      dp[len] = q[i];
    } else {
      l = 1;
      r = len;
      while (l < r) { // 二分查找第1个大于q[i] 的数
        int mid = (l + r) / 2;
        if (dp[mid] >= q[i]) r = mid;
        else l = mid + 1;
      }
      dp[l] = q[i]; // 替换
    }
  }

  printf("%d", len);

  return 0;
}

复杂度分析（优化后）

  • 时间复杂度： 外层循环遍历 n 个元素。对于每个元素，我们在 tails 数组上执行一次二分查找。tails 数组的长度最多为 n。二分查找的时间复杂度是 O(log k)，其中 k 是 tails 的当前长度 (k <= n)。所以总时间复杂度是 O(n log n)。
  • 空间复杂度： 需要 tails 数组来存储信息，其最大长度为 n。所以空间复杂度是 O(n)。

示例：最长公共子序列 (LCS)

简单背包类型动态规划

简单区间类型动态规划

总结与建议

  • 动态规划是一种强大的思想，核心是 拆分问题、记录结果、组合答案。
  • 关键在于找到 状态定义 和 状态转移方程。
  • 多练习！ DP 的掌握需要通过解决大量的题目来培养感觉和熟练度。从简单的问题开始，比如斐波那契、爬楼梯、简单路径计数，然后逐步挑战更复杂的经典问题，如背包、LCS、LIS 等。
  • 画表格/状态图： 对于一些问题，手动模拟填表过程或者画出状态之间的依赖关系，有助于理解状态转移。
  • 不要怕困难： DP 问题往往初看很难，但一旦想清楚了状态和转移，代码实现通常并不复杂。
Navigation

Type to search…

↑↓ navigate↵ selectEsc close