引言

动态规划(Dynamic programming,简称dp)是是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法
DP应用于子问题重叠的情况：

  1. 刻画最优解的结构特征
  2. 尝试递归地定义最优解的值
  3. 计算子结构最优解
  4. 利用计算出的信息构造出最优解

    思考方式

    从集合的角度思考dp问题
  • 状态表示
    • 集合：所有从f[1,1]走到f[i,j]的路线
    • 属性：count，max，min
  • 状态计算
    • 集合的划分
    • 限制：不重不漏

DP三问

  • 我是谁？ —— 状态的属性
  • 我从哪里来？ —— 状态的计算
  • 要到哪里去？ —— 状态的表示

分类

背包dp

用背包装物品，求最大价值

01背包

二维

物品的个数只有0或1个
i为前i个物品的方案，j为最大容量
f[i][j]
从
f[i-1][j]
(不选第i物品，价值与i-1的情况相同)
和
f[i-1][j-v[i]] + w[i]
(选择第i件物品，由于最大容量为j，f[i-1][j-v[i]]为能存入第i件物品的最大价值，加上w[i]，为f[i-1][j]的价值)
中取

一维优化

由于f[i]的状态只与f[i-1]的状态有关，可以优化为一维
直接删去[i]维
f[j]
从
f[j]
和
f[j-v[i]] + w[i]
中取
for (j = v[i]; j <= m; j ++ )的过程中 f[j-v[i]] 数据会由小到大变为第i层的数据，f[k] (k为后序情况) 就会使用到第i层的情况
所以采用逆序遍历 for (int j = m; j >= v[i]; j -- ) 由于数据是由大到小改变的，f[j]只会使用到第i-1层的数据

代码
  1. // 二维
  2. for (int i = 1;i <= n; i ++ ) {
  3.     for (int j = v[i]; j <= m;j ++) {
  4.         f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
  5.     }
  6. }
  7. // 一维
  8. for (int i = 1;i <= n; i ++ ) {
  9.     for (int j = m;j >= v[i] ; j -- ) {
  10.         f[j] = max(f[j],f[j-v[i]] + w[i];
  11.     }
  12. }

完全背包

每种物品都有无限件可用

状态转移方程
f[i][j]=max{f[i-1][j-k*c[i]]+k*w[i] |0<=k*c[i]<=j}
列举一下更新次序的内部关系
f[i , j ] = max( f[i-1,j] , f[i-1,j-v] + w , f[i-1,j-2v] + 2w , f[i-1,j-3v]+3w , .....)
f[i , j-v] = max( f[i-1,j-v] , f[i-1,j-2v] + w , f[i-1,j-3v]+2w , .....)
由上两式，可得出如下递推关系：
f[i][j] = max(f[i-1][j], f[i][j-v]+w)
核心代码可以优化为

  1. for(int i = 1 ; i <=n ;i++)
  2. {
  3.     for(int j = 0 ; j <=m ;j++)
  4.     {
  5.         f[i][j] = f[i-1][j];
  6.         if(j-v[i]>=0)
  7.             f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
  8.     }
  9. }
  10. // 最大价值为 Max(f[i][m])

进一步优化，由于完全背包的状态转移方程只依赖i层数据，所以从小到大遍历

  1. for(int i = 1 ; i<=n ;i++)
  2. {
  3.     for(int j = v[i] ; j<=m ;j++)
  4.     {
  5.         f[j] = max(f[j],f[j-v[i]]+w[i]);
  6.     }   
  7. }

多重背包

有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

朴素做法
  1. for (int i = 1; i <= n; i++)
  2.     for (int j = 0; j <= m; j++)
  3.         for (int k = 0; k <= s[i] and k * v[i] <= j; k++)
  4.             f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);

二进制优化

把s[i]个物品优化成log s[i] 个 物品，转为 01 背包

  1. #include <iostream>
  3. using namespace std;
  5. const int N = 25000, M = 2000;
  7. int f[N], v[N], w[N];
  9. int main()
  10. {
  11.     int n, m;
  12.     cin >> n >> m;
  13.     int cnt = 0;
  14.     for (int i = 0;i<n;i++) {
  15.         int a, b, s;
  16.         cin >> a >> b >> s;
  17.         int k = 1;
  18.         while (k<=s) {
  19.             cnt ++ ;
  20.             v[cnt] = a * k;
  21.             w[cnt] = b * k;
  22.             s -= k;
  23.             k *= 2;
  24.         }
  25.         if (s>0) {
  26.             cnt ++;
  27.             v[cnt] = a * s;
  28.             w[cnt] = b * s;
  29.         }
  30.     }
  31.     n = cnt;
  32.     for (int i = 1;i<=n;i++) {
  33.         for (int j = m;j>=v[i];j--) {
  34.             f[j] = max(f[j] , f[j -v[i]] + w[i]);
  35.         }
  36.     }
  37.     cout << f[m] << endl;
  38.     return 0;
  39. }

分组背包

有N件物品和一个容量为V的背包。第i件物品的费用是v[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

状态转移方程
f[j] = max(f[j], f[j - v[i][k]] + w[i][k])

线性dp

数字三角形

  1.         7
  2.       3   8
  3.     8   1   0
  4.   2   7   4   4
  5. 4   5   2   6   5

求一条路径，使得路径上的数字和最大

状态转移方程
到达f[i,j]的路径可以分为两类子集，一类从左上（下），一类从右上（下）
自底向上 f[i][j] += max(f[i+1][j],f[i+1][j+1])
自顶向下 f[i][j] += max(f[i-1][j],f[i-1][j-1])

最长上升子序列

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少

状态表示
f[i]表示以i为结尾的最长上升子序列长度
状态转移方程
f[i]默认为1
f[i] = max(f[k]+1) DP - 图1

最长公共子序列

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少

状态表示
f[i,j]表示A里面前i个字符与B里面前j个字符想匹配的个数
状态转移方程
f[i][j] = max(f[i-1][j],f[i][j-1])
f[i][j] = max(f[i][j],f[i-1][j-1]+1) A[i] == B[j]

最长上升子序列

贪心思维

维护一个最长上升子序列

区间dp

计数dp

数位dp

状压dp

树形dp

记忆化搜索