动态规划

背包问题

0-1背包

转移方程：\(dp[i][j]=max(dp[i-1][j], dp[i-1][j-v[i]]+w[i])\)

1
2
3
4
5
6
7
8
9
10
int v[N], w[N], dp[N][N];
int n, m;

// dp[i][j] 为考虑1-i个物品，背包容积为j时的最大价值
for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
        if(j >= v[i]) dp[i][j] = max(dp[i-1][j-v[i]]+w[i], dp[i-1][j]); 
        else dp[i][j] = dp[i-1][j];
    }
}

在计算 \(dp[i][j]\) 时，只会用到\(dp[i-1][j]\)，不会用到比\(i\)更早的状态。

因此可以考虑因此可以去掉第一个维度，反复利用同一个一维数组。

转移方程：$dp[j] = max(dp[j], dp[i-1][j-v[i]]+w[i]) $

1
2
3
4
5
6
7
8
int v[N], w[N], dp[N][N];
int n, m;

for(int i = 1; i <= n; i++){
    for(int j = m; j >= 1; j--){
        if(j >= v[i]) dp[j] = max(dp[j-v[i]]+w[i], dp[j]);
    }
}

完全背包

转移方程：\(dp[i][j]=max(dp[i-1][j], dp[i][j-v[i]]+w[i])\)

1
2
3
4
5
6
7
8
9
int v[N], w[N], dp[N][N];
int n, m;

for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
        if(j >= v[i]) dp[i][j] = max(dp[i][j-v[i]]+w[i], dp[i-1][j]);
        else dp[i][j] = dp[i-1][j];
    }
}

多重背包

转移方程：\(dp[i][j]=max(dp[i-1][j], dp[i-1][j-k*v[i]]+w[i]*k), k=0,1,..,s[i]\)

1
2
3
4
5
6
7
8
9
10
int v[N], w[N], s[N], dp[N][N];
int n, m;
   
for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
        dp[i][j] = dp[i-1][j];
        for(int k = 0; k <= s[i] && v[i]*k <= j; k++) 
            dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]*k]+k*w[i]);
    }
}

分组背包

每组物品有若干个，同一组内的物品最多只能选一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// s[i] 第i组物品个数
// v[i][j] i组中第j个物品的体积
// w[i][j] i组中第j个物品的价值
int s[N], v[N][N], w[N][N], dp[N][N];


for(int i=1; i<=n; i++){  // 遍历组编号
    for(int j=1; j<=m; j++){	// 遍历背包容积
        dp[i][j] = dp[i-1][j];
        for(int k=1; k<=s[i]; k++){  // 遍历组内物品
            if(v[i][k] <= j) 
                dp[i][j] = max(dp[i][j], dp[i-1][j-v[i][k]]+w[i][k]);
        } 
    }
}

线性DP

  • 子序列不要求在原序列中连续
  • 字串要求连续

70. 爬楼梯 - 力扣（LeetCode）

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

198. 打家劫舍 - 力扣（LeetCode）

最长递增子序列

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

初始化 \(dp[i] = 1, (i=1,..,n)\) 表示以\(nums[i]\) 结尾的最长单调递增子序列的长度

\(dp[i] = \underset{j<i\ and\ nums[j] < nums[i]}{max}\{dp[j] + 1\}\)

\(ans = max(dp[1],dp[2],...,dp[n])\)

时间复杂度\(O(n^2)\)

n大于\(1e^5\)时 \(O(n^2)\)时间复杂度会导致超时

定义\(dp[i]\)表示长度为\(i+1\)的最长递增子序列最后一个数字的最小值

利用\(dp\)数组的单调性，通过二分查找找到大于等于\(nums[i]\)位置

时间复杂度\(O(n^2)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int dp[N], nums[N];

int main(){
    int n; cin >> n;
    for(int i=1; i<=n;i++) scanf("%d", &nums[i]);
    
    int ans = 0;
    for(int i=1; i<=n; i++){
        if(ans == 0 || dp[ans-1] < nums[i]) dp[ans++] = nums[i];
        else{
            int l = 0, r = ans-1;
            while(l < r){
                int mid = (l + r) >> 1;
                if(dp[mid] >= nums[i]) r = mid;
                else l = mid + 1;
            }
            if(dp[l] > nums[i]) dp[l] = nums[i];
        }
    }
    cout << ans << endl;
    return 0;
}

最长公共子序列

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

\(dp[i][j]\) 表示字符串$A[0:i] \(与\)B[0:j]$的最长公共子序列长度

初始化: \(dp[i][j] = 0\) 任何序列和空串的最长公共子序列长度都为0

转移方程:

（1）\(A[i]=B[i]\) 时，\(dp[i][j] = dp[i-1][j-1] + 1\)

（2）\(A[i]\neq B[i]\) 时，\(dp[i][j] = max(dp[i-1][j], dp[i][j-1])\)

编辑距离

给出字符串A和B，求将A转换成B所使用的最少操作数

对每个字符可进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

\(dp[i][j]\) 表示字符串\(A[0:i]\)变成\(B[0:j]\)的最少操作数（重点关注各自的最后字符）

初始化： （任何序列和空串的编辑距离均为序列长度）

  • \(dp[i][0]=i,(i=1,2,..,n)\)
  • \(dp[0][j]=j,(j=1,2,...,n)\)

转移方程

\(if\ A[i]==B[i],\ dp[i][j] = dp[i-1][j-1]\)

\(else\ dp[i][j]=min(dp[i-1][j], dp[j][i-1], dp[i-1][j-1]) + 1\)

其中

  • \(dp[i-1][j],dp[i][j-1]\) 可以看成插入或者删除一个字符
  • \(dp[i-1][j-1]\)为交换两个字符

区间DP

所有的区间dp问题枚举时，第一维通常是枚举区间长度，并且一般 len = 1 时用来初始化，枚举从 len = 2 开始；第二维枚举起点 i （右端点 j 自动获得，j = i + len - 1）

1
2
3
4
5
6
7
8
9
10
11
for (int len = 1; len <= n; len++) {         // 区间长度
    for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点
        int j = i + len - 1;                 // 区间终点
        if (len == 1) dp[i][j] = 初始值
		else{
        	 for (int k = i; k < j; k++) {        // 枚举分割点，构造状态转移方程
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
            }
        }
    }
}

石头合并

合并 N 堆石子，每次只能合并相邻的两堆石子，求最小代价

（最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并）

\(dp[i][j]\) 表示将 𝑖 到 𝑗 这一段石子合并成一堆的方案的集合，属性 Min

利用前缀和计算区间和

转移方程：

  1. \(i<j\) 时，\(dp[i][j] = \underset{i\le k\le j-1}{min} \{dp[i][k] + dp[k+1][j] + s[j] - s[i-1]\}\)

  2. \(i=j\) 时， \(dp[i][j] = 0\) （合并一堆石子代价为 0）

计数类DP

整数划分

一个正整数n可以表示成若干个正整数之和，形如：\(n=n_1+n_2+…+n_k\)，其中\(n_1≥n_2≥…≥n_k,k≥1\)。

这样的一种表示称为正整数n的一种划分。给定一个正整数n，求出n共有多少种不同的划分方法。

完全背包的解法 \(O(n^3)\)

状态定义: \(dp[i][j]\) 从1-i中选体积刚好为j的方案数量,

状态计算： \(dp[i][j] = \underset{k*i\le j}{\sum} \{dp[i-1][j-i*k]\}\)

image-20240730131454674 
1
2
3
4
5
6
7
8
9
10
11
int dp[N][N]; // dp[i][j] 从1-i中选体积刚好为j的方案数量

for(int i = 0; i <= n; i++) dp[i][0] = 1;  // 一个数也不选也是一种方案

for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
        for(int k = 0; j - k * i >= 0; k++){
            dp[i][j] += dp[i-1][j - i*k];
        }
    }
}

完全背包优化 \(O(n^2)\)

\(dp[i][j] = dp[i-1][j]+dp[i-1][j-i]+dp[i-1][j-2i]+dp[i-1][j-3i]+...+dp[i-1][j-ki]\)

\(dp[i][j-i] = \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ dp[i-1][j-i]+dp[i-1][j-2i]+dp[i-1][j-3i]+...+dp[i-1][j-ki]\)

将\(dp[i][j-i]\)代入 \(dp[i][j]\) 得到 \(dp[i][j] = dp[i-1][j]+dp[i][j-i]\)

优化一维：\(dp[j] = dp[j]+dp[j-i]\)

1
2
3
4
5
6
7
8
int dp[N];
dp[0] = 1;
    
for(int i = 1; i <= n; i++){
    for(int j = i; j <= n; j++){
        dp[j] = dp[j] + dp[j - i]
    }
}

计数DP方案

image-20240730135056199 
1
2
3
4
5
6
7
8
9
10
11
12
int dp[N][N];
dp[0][0] = 1;
    
for(int i = 1; i <= n; i++){
    for(int j = 1; j <= i; j++){
        dp[i][j] = (dp[i - 1][j - 1] + dp[i - j][j]);
    }
}

int res = 0;
for(int i=1; i<=n; i++) res += dp[n][i];

数位统计DP

状态压缩DP

树形DP

记忆化搜索