数字三角形
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
1
2
3
4
5
| 7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
|
这是一道非常简单的DP问题
状态表示 可以用f[i][j] 来表示某个某一行某一列的最大值
**状态转移 ** 上一行的前两个之中的最大值
代码中有一些细节需要注意一下
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
26
27
28
29
30
31
32
33
34
35
| #include<iostream>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int a[N][N], dp[N][N];
int n;
int main()
{
cin >> n;
for(int i = 1; i <= n ; i++)
for(int j = 1; j <= i; j++)
cin >> a[i][j];
for(int i = 1; i <= n ; i++)
for(int j = 1; j <= i + 1; j++)
dp[i][j] = -INF;
for(int i = 1; i <= n ; i++)
for(int j = 1; j <= i; j++)
{
if(j == 1)
dp[i][j] = dp[i - 1][j] + a[i][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][ j - 1]) + a[i][j];
}
int ret = -INF;
for(int i = 1; i <= n; i++)
ret = max(dp[n][i],ret);
cout << ret;
return 0;
}
|
最长上升子序列
给定一个长度为 N的数列，求数值严格单调递增的子序列的长度最长是多少。
简单的线性DP题目
状态表示: dp表示每个数字结尾的最大子序列长度
状态转移: 数字结尾比当前数字小的最大长度+1
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
26
27
| #include<iostream>
using namespace std;
const int N = 1010;
int a[N], dp[N];
int n;
int main()
{
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < n; i++) dp[i] = 1;
for(int i = 1; i < n; i++)
{
for(int j = 0; j < i; j++)
if(a[j] < a[i]) dp[i] = max(dp[i],dp[j] + 1);
}
int ret = 0;
for(int i = 0; i < n; i++) ret = max(ret, dp[i]);
cout <<ret;
return 0;
}
|
如果要输出最长子序列长度的话我们可以记录状态转移的过程,最后输出的时候还原一下状态就可以
对于N较大时我们仍可以优化算法, 进一步提高时间复杂度
根据动态规划我们刚发现只要下一个数的最大值大于最后一个数的最大值, 最长子序列的长度即可增加1.
所以我们维护一个不断扩大的数组来减少时间复杂度.
我们可以维护一个单调队列, 如果下一个数大于队列最后一个数的值的话, 向队尾增加一个元素, 否则我们找到队列中大于x的最小值, 将它替换为x, 不断缩小队列内数值的大小.
我们可以用二分在队列内找到一个大于x的最小值进行替代.
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
26
27
28
29
30
31
32
| #include<iostream>
using namespace std;
const int N = 100000 + 10;
int a[N], q[N];
int n;
int main()
{
cin >> n;
int len = 0;
for(int i = 0; i < n; i++)
{
int x;
cin >> x;
q[0] = -0x3f3f3f3f;
int l = 0, r = len;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(x > q[mid]) l = mid;
else r = mid - 1;
}
len = max(len, r+1);
q[r+1] = x;
}
cout << len;
return 0;
}
|
最长公共子序列
给定两个长度分别为 N和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
状态表示
- 集合: 表示的集合是第一个字符串前i个字符和第二个字符串前j个字符的集合
- 属性: 表示的是公共子序列的最大值
状态转移
四种状态转移到新的状态分别为
1
2
3
4
| f[i - 1][j - 1] 表示不包含 i j 两个字符
f[i - 1][j] 表示包含j不包含i(表示的集合是包含此内容,但不等价)
f[i][j - 1] 表示包含i不包含j(表示的集合是包含此内容,但不等价)
f[i - 1][j - 1] + 1 表示包含ij
|
第二种状态和第三种状态转移一定是包含第一种状态的,所以我们在写代码过程中不需要单独写第一种状态转移
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
26
| #include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000 + 10;
char a[N], b[N];
int f[N][N];
int main()
{
int n,m;
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= m; i++) cin >> b[i];
for(int i = 1; i <= n; i++)
for(int j = 1; j <=m; j++)
{
f[i][j] = max(f[i - 1][j] , f[i][j - 1]);
if(a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
}
cout << f[n][m];
return 0;
}
|
最短编辑距离
给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：
- 删除–将字符串
A 中的某个字符删除。
- 插入–在字符串
A 的某个位置插入某个字符。
- 替换–将字符串
A 中的某个字符替换为另一个字符。
现在请你求出，将 A 变为 B 至少需要进行多少次操作。
状态表示: 类似于最长公共子序列,
- 集合:
f[i][j] 表示前i个长度和前j个长度
- 属性: 操作次数的最小值
状态转移:
对于A等于0的情况, B的长度就等于最小操作次数
每增加一个字符,我们就要分情况判断
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
26
27
28
29
30
31
32
33
34
35
36
37
| #include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
char a[N], b[N];
int n, m;
int f[N][N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
cin >> m;
for(int i = 1; i <= m; i++) cin >> b[i];
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] + 1, f[i][j - 1] + 1);
if(a[i] == b[j]) f[i][j] = min(f[i][j],f[i - 1][j - 1]);
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}
cout << f[n][m];
return 0;
}
|
