算法基础-动态规划

背包问题

01.01背包问题

题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i，用空格隔开，分别表示第 i件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V\le 10000<v_i,w_i≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

题解

时间复杂度

O(n \cdot m)

核心思想

version1:2维暴力(朴素)做法

f[i][j] —> 在不超过j容积的情况下前选择前i个物品的最优解

version2:1维优化版本

由二维可知我们跟新f[i][j] 只需要用到f[i - 1]状态 也就是前i - 1个物品的状态又因为f[i - 1]已经是最优解 所以我们可以用所谓的的滚动数组进行优化 即: if(j ≥ v)f[j] = max(f[j], f[j - v] + w); 如果从前往后遍历的话我们用f[i - 1] 来跟新 f[i] 的时候就不能保证对于f[i]来说是用同一时期的f[i - 1]进行跟新会导致数据错误 总结来说就一句话 如果用到上层状态就逆序遍历 否则就顺序遍历

核心函数

// version1

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

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

代码实现

#include <iostream>

using namespace std;

const int N = 1010;
int n, m;
int v, w;
int f[N];

int main (){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> v >> w;
        for(int j = m; j >= v; j --)
            f[j] = max(f[j], f[j - v] + w);
    }
    cout << f[m] << endl;
    return 0;
}

02.完全背包问题

03.多重背包问题

04.多重背包问题II

05分组背包问题

线性DP

01.数字三角形

02.最长上升子序列

03.最长上升子序列II

04.最长公共子序列

05.最短编辑距离

题目描述

给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：

1. 删除–将字符串 A 中的某个字符删除。
2. 插入–在字符串A 的某个位置插入某个字符。
3. 替换–将字符串A 中的某个字符替换为另一个字符。

现在请你求出，将A 变为B 至少需要进行多少次操作。

输入格式

第一行包含整数 n，表示字符串 A 的长度。

第二行包含一个长度为 n 的字符串 A。

第三行包含整数 m，表示字符串 B 的长度。

第四行包含一个长度为 m 的字符串 B。

字符串中均只包含大小写字母。

输出格式

输出一个整数，表示最少操作次数。

数据范围

1 \le n, m \le 1000

输入样例：

10 
AGTCTGACGC
11 
AGTAAGTAGGC

输出样例：

4

题解

时间复杂度

O(n^2)

状态表示:f[i][j]

集合:将a[1\sim i]变成b[1 \sim j]的操作方式

属性:min

状态计算

有三种操作，所以有三个子集 ok子集划分完了 考虑状态转移的时候 先考虑如果我没有进行这个操作应该是什么状态 然后考虑你进行这一步操作之后会对你下一个状态造成什么影响 然后再加上之前状态表示中你决策出来的那个DP属性 这样就可以自然而然地搞出来转移方程啦

• 删除操作： ​

把a[i]删掉之后a[1\sim i]和b[1\sim j]匹配 ​

所以之前要先做到a[1\sim (i-1)]和b[1\sim j]匹配 ​

f[i-1][j] + 1

• 插入操作：

插入之后a[i]与b[j]完全匹配，所以插入的就是b[j]

那填之前a[1\sim i]和b[1\sim (j-1)]匹配

f[i][j-1] + 1

• 替换操作：

把a[i]改成b[j]之后想要a[1\sim i]与b[1\sim j]匹配

那么修改这一位之前，a[1\sim (i-1)]应该与b[1\sim (j-1)]匹配

f[i-1][j-1] + 1

但是如果本来a[i]与b[j]这一位上就相等，那么不用改，即

f[i-1][j-1] + 0

好的那么f[i][j]就由以上三个可能状态转移过来，取个min

细节:

f[0][j]如果a初始长度就是0，那么只能用插入操作让它变成b

f[i][0]如果同样地，如果b的长度是0，那么a只能用删除操作让它变成b

核心函数(转移方程):

for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
            int flg = a[i] != b[j];
            f[i][j] = min(f[i - 1][j - 1] + flg, f[i][j]);
        }

代码实现:

#include <iostream>
#include <cstring>

using namespace std;
const int N = 1010; 

int f[N][N];
char a[N], b[N];
int n, m;

int main(){
    cin >> n >> a + 1 >> m >> b + 1;
    memset(f, 0x3f, sizeof f);
    for(int i = 0; i <= n; i ++)
        f[i][0] = i;
    for(int i = 0; i <= m; i ++)
        f[0][i] = i;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
            int flg = a[i] != b[j];
            f[i][j] = min(f[i - 1][j - 1] + flg, f[i][j]);
        }
    cout << f[n][m] << endl; 
    return 0;
}

06.编辑距离

题目描述

给定 n 个长度不超过 10 的字符串以及 m 次询问，每次询问给出一个字符串和一个操作次数上限。

对于每次询问，请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

输入格式

第一行包含两个整数 n 和 m。

接下来n 行，每行包含一个字符串，表示给定的字符串。

再接下来 m 行，每行包含一个字符串和一个整数，表示一次询问。

字符串中只包含小写字母，且长度均不超过 10。

输出格式

输出共 mm 行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。

数据范围

1 \le n, m \le 1000,

输入样例：

3 2
abc
acd
bcd
ab 1
acbd 2

输出样例：

1
3

题解

区间DP

01.石子合并

数位DP

01.整数划分

题目描述

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

我们将这样的一种表示称为正整数 n 的一种划分。

现在给定一个正整数 n，请你求出 n 共有多少种不同的划分方法。

输入格式

共一行，包含一个整数 n。

输出格式

共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对 10^9 + 7 取模。

数据范围

1 \le n \le 1000

输入样例:

5

输出样例：

7

题解

时间复杂度

O(n^2)

思想和完全背包一致

f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2i] + f[i - 1][j - 3i]

f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - 2i] + f[i - 1][j - 3i]

f[i][j] = f[i - 1][j] + f[i][j - i]

压缩之后:

f[j] += fj - i

核心函数

for(int i = 1; i <= n; i ++)
    for(int j = i; j <= n; j ++)
        f[j] += f[j - i];

代码实现

#include <iostream>

using namespace std; 

const int N = 1010, MOD = 1e9 + 7;

int n, f[N];

int main(){
    cin >> n; 
    f[0] = 1;
    for(int i = 1; i <= n; i ++)
        for(int j = i; j <= n; j ++)
            f[j] = (f[j] + f[j - i]) % MOD;
    cout << f[n] << endl; 
    return  0;
}

状态压缩DP

01.蒙德里安的猜想

02.最短Hamilton路径

树形DP

01.没有上司的舞会

记忆化搜索

01.滑雪