线性DP入门

博主： spirit
发布时间：2021 年 01 月 21 日
1207 次浏览
暂无评论
1317字数
分类：线性DP

## 一、什么是动态规划？

动态规划算法没有固定的算法模板，更像是一种思考问题的方式。动态规划算法把原问题视作若干个重叠子问题的逐层递进，每个子问题的求解过程都构成一个 **“阶段”** 。在完成前一个阶段的计算后，动态规划才会执行下一个阶段的计算。

- 动态规划算法求解问题的三个基本条件：
  
  - **无后效性：** 动态规划要求已经求解的子问题不受后续阶段的影响，以保证对每一阶段的计算能够按顺序、不重复地执行。
  - **最优子结构性质：** 在动态规划算法求解问题的过程中，下一阶段的解应该能由前面各阶段子问题的最优解导出。
  - **子问题重叠性：** 动态规划所针对的问题还有另外一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复，称为子问题重叠性质。
- 动态规划算法求解问题的一般思路：
  
  - **”状态“ “阶段” 和 ”决策“** 是构成动态规划算法的三要素，因此在用动态规划算法解决问题的过程中第一件事就是选择一个合适的 **“状态”** 。
  - **”状态转移方程“：** 动态规划算法把相同的计算过程用于各阶段的同类子问题，就好像把一个固定的公式在格式相同的若干组数据上运行。这个计算过程就被称为 **”状态转移方程“** 。

动态规划算法实际运用过程中灵活多变，思维难度较高。同时动态规划算法的类型较多，常见的DP问题如：线性DP，背包问题，区间DP，数位DP，概率DP等等，优化的小技巧更是五花八门。因此动态规划算法在算法竞赛中是比较常见也比较难的一个模块。在程序设计基础课程中，我们只学习一些基本概念和几个经典的线性DP模型。

## 二、几个常见的线性DP模型

### 最长上升子序列（LIS）问题

- [例题 SDUT1299](https://acm.sdut.edu.cn/onlinejudge3/problems/1299)
- $LIS$ 问题：
  
  - 状态表示： $dp_i$ 表示以 $A_i$ 结尾的 ”最长上升子序列“ 的长度。
  - 阶段划分 ： 子序列的结尾位置（数列 $A$ 中的位置，从前到后）。
  - 转移方程： $dp_i = max$ { $dp_j + 1 | 0 \leq j < i, A_j < A_i$ }
  - 边界： $dp_0 = 0$
  - 目标： $max$ { $dp_i | 1 \leq i \leq N$ }
- 代码：
  
  ```cpp
  #include <algorithm>
  #include <cstdio>
  #include <cstring>
  #include <iostream>
  
  using namespace std;
  const int N = 1005;
  int dp[N], a[N];
  
  int main() {
      int n, res = 0;
      dp[0] = 0, a[0] = -1;
      cin >> n;
      for (int i = 1; i <= n; i++) {
          scanf("%d", &a[i]);
          for (int j = 0; j < i; j++)
              if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
          res = max(res, dp[i]);
      }
      cout << res << endl;
      return 0;
  }
  ```

### 最长公共子序列（LCS）问题

- [例题 SDUT2080](https://acm.sdut.edu.cn/onlinejudge3/problems/2080)
- $LCS$ 问题：
  
  - 状态表示： $dp_{i, j}$ 表示前缀子串 $A[1, i]$ 与 $B[1, j]$ 的 “最长公共子序列” 的长度。
  - 阶段划分： 已经处理的前缀长度（两个字符串中的位置，即一个二维坐标）。
  - 转移方程： $dp_{i, j} = max$ { $dp_{i-1, j}, dp_{i, j-1}, (dp_{i-1, j-1}     + 1 | A_i = B_j)$ }
  - 边界： $dp_{i, 0} = dp_{0, j} = 0$
  - 目标： $dp_{N, M}$
- 代码：
  
  ```cpp
  #include <algorithm>
  #include <cstdio>
  #include <cstring>
  #include <iostream>
  
  using namespace std;
  const int N = 505;
  char A[N], B[N];
  int dp[N][N];
  
  int main() {
      int n, m;
      while (~scanf("%s %s", A + 1, B + 1)) {
          n = strlen(A + 1);
          m = strlen(B + 1);
          for (int i = 0; i <= n; i++) dp[i][0] = 0;
          for (int j = 0; j <= m; j++) dp[0][j] = 0;
          for (int i = 1; i <= n; i++)
              for (int j = 1; j <= m; j++) {
                  dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                  if (A[i] == B[j])
                      dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
              }
          printf("%d\n", dp[n][m]);
      }
      return 0;
  }
  ```

### 数字三角形问题

- [例题 SDUT1730](https://acm.sdut.edu.cn/onlinejudge3/problems/1730)
- 数字三角形问题：
  
  - 状态表示： $dp_{i, j}$ 表示从左上角走到第 $i$ 行第 $j$ 列，和最大是多少。
  - 阶段划分： 路径的结尾位置（矩阵中的行、列位置，即一个二维坐标）。
  - 转移方程： $dp_{i, j} = A_{i, j} + max$ { $dp_{i-1, j}, dp_{i-1, j-1}$ }
  - 边界： $dp_{1, 1} = A_{1, 1}$
  - 目标： $max$ { $dp_{N, j}$ }
- 代码：
  
  ```cpp
  #include <algorithm>
  #include <cstdio>
  #include <cstring>
  #include <iostream>
  
  using namespace std;
  const int N = 105;
  int a[N][N], dp[N][N];
  
  int main() {
      int n, res = 0;
      cin >> n;
      for (int i = 1; i <= n; i++)
          for (int j = 1; j <= i; j++) scanf("%d", a[i] + j);
      for (int i = 1; i <= n; i++)
          for (int j = 1; j <= i; j++)
              dp[i][j] = a[i][j] + max(dp[i - 1][j], dp[i - 1][j - 1]);
      for (int i = 1; i <= n; i++) res = max(res, dp[n][i]);
      cout << res << endl;
      return 0;
  }
  ```

## 记忆化搜索

- [例题 SDUT2176](https://acm.sdut.edu.cn/onlinejudge3/problems/2176)
- 代码：
  
  ```cpp
  #include <algorithm>
  #include <cstdio>
  #include <cstring>
  #include <iostream>
  
  using namespace std;
  const int N = 25, INF = 0x3f3f3f3f;
  int dp[N][N][N];
  
  /* 对比正确答案，思考为什么用下面这个函数会超时？
  int f(int a, int b, int c) {
      if (a <= 0 || b <= 0 || c <= 0) return 1;
      if (a > 20 || b > 20 || c > 20) return f(20, 20, 20);
      int res;
      if (a < b && b < c)
          res = f(a, b, c - 1) + f(a, b - 1, c - 1) - f(a, b - 1, c);
      else
          res = f(a - 1, b, c) + f(a - 1, b - 1, c) + f(a - 1, b, c - 1) -
                f(a - 1, b - 1, c - 1);
      return res;
  }
  */
  int f(int a, int b, int c) {
      if (a <= 0 || b <= 0 || c <= 0) return 1;
      if (a > 20 || b > 20 || c > 20) return f(20, 20, 20);
      if (dp[a][b][c] != INF) return dp[a][b][c];
      int res;
      if (a < b && b < c)
          res = f(a, b, c - 1) + f(a, b - 1, c - 1) - f(a, b - 1, c);
      else
          res = f(a - 1, b, c) + f(a - 1, b - 1, c) + f(a - 1, b, c - 1) -
                f(a - 1, b - 1, c - 1);
      return dp[a][b][c] = res;
  }
  
  int main() {
      int a, b, c;
      memset(dp, 0x3f, sizeof dp);
      while (~scanf("%d %d %d", &a, &b, &c)) {
          printf("%d\n", f(a, b, c));
      }
      return 0;
  }
  ```

最后修改：2021 年 02 月 17 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

线性DP入门

spirit • 2021 年 01 月 21 日

## 一、什么是动态规划？

## 二、几个常见的线性DP模型

### 最长上升子序列（LIS）问题

### 最长公共子序列（LCS）问题

### 数字三角形问题

## 记忆化搜索

线性DP入门

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Kattis Message （状态机模型 + 矩阵快速幂）

数论进阶——莫比乌斯反演

Codeforces Round #703 (Div. 2)

SDUT 2021 Winter Individual Contest - E

Kattis Fruit Slicer （计算几何 + 扫描线）

Ubuntu24.04 配置虚空终端

SDUT 2021 Winter Individual Contest - D

Gym 101147 A-The game of Osho

Kattis Terraced fields （数位DP）

数论进阶——莫比乌斯反演

线性DP入门

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

线性DP入门

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款