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

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 动态规划

![](https://img.dailyup.xyz/originals/8208463044478-b83c0b66-b347-4977-a8cb-5f0e26c4ac24.png)

## 什么是动态规划

来自维基百科的定义：动态规划（英语：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 是第零项，而不是第一项


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

代码如下：

```cpp
#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)` 为例：

![](https://img.dailyup.xyz/optimized/8208463045089-5d92132a-a774-4924-a0a3-91e9b8344557.png)


- 想求 `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` 越大，程序会越慢，可能会慢到无法接受。

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

```

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

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

```cpp
#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)$ 。

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

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

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

```cpp
#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` 数组。可以用两个变量滚动计算。

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

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

```cpp
#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]` 中的最大值即可。

**代码实现**

```cpp
#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)$。

优化的参考代码如下：

```cpp
#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) 中的最大值**。

**参考代码**

```cpp
#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 的长度。

**参考代码**

```cpp
// 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 问题往往初看很难，但一旦想清楚了状态和转移，代码实现通常并不复杂。

Source: https://cppguide.xyz/algorithm/dp/index.mdx