新人须知
新人须知

动态规划

什么是动态规划

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

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

再看 Fibonacci 数列

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

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

{F0=0F1=1Fn=Fn−1+Fn−2\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(2n)O(2^n) 降为 O(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)O(n)；另外，要求 fib(n)，我们需要计算 fib(n-1) 和 fib(n-2)，一直到 fib(1) 和 fib(0)，这意味着我们的空间复杂度也为 O(n)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(n) 降低到 O(1)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(n)，但空间复杂度是恒定的，不再随输入的大小而增大，因此空间复杂度为 O(1)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，找到一具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

例如，对于一组 nn 个整数，n=7n = 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] 中的最大值即可。

DP代码实现

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

最长递增子序列 (LIS)

最长公共子序列 (LCS)

简单背包类型动态规划

简单区间类型动态规划

总结与建议

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

关联

  • [[2025-04-21_card01_动态规划问题-杂乱内容]]
ON THIS PAGE