动态规划
动态规划（Dynamic Programming，简称DP）。动态规划分为线性dp、树形dp、数位dp等等。
注意：本文图文并茂
将提供以下图文链接供大家理解：
图文链接：
飞书图解链接🎉🎉🎉
密码：335#47C4
1. dp起源
数字三角形
P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles
案例1：
4
1
4 6
8 3 9
5 7 2 1
案例2：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
方法一：深搜(dfs)
代码如下:
AC代码，展开查看
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N][N];
int n, ans = 0;
void dfs(int x, int y, int sum){
if(x == n - 1) {
ans = max(ans, sum);
return;
}
dfs(x + 1, y, sum + a[x + 1][y]);
dfs(x + 1, y + 1, sum + a[x + 1][y + 1]);
}
int main(){
cin >> n;
for(int i = 0; i < n; i ++ ){
for(int j = 0; j <= i; j ++ ){
cin >> a[i][j];
}
}
dfs(0, 0, a[0][0]);
cout << ans << "\n";
return 0;
}
深搜代码时间复杂度为: \(n!\)，n为行数，显然会超时。
方法二：记忆化搜索
记忆化搜索过程: 记忆化搜索从搜索树的下面开始向上回溯。
代码如下:
AC代码，展开查看
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], f[N][N];
int n;
int dfs(int x, int y){
if(f[x][y]) return f[x][y]; // 便面重复遍历
if(x == n - 1) f[x][y] = a[x][y]; // 树根
else f[x][y] = a[x][y] + max(dfs(x + 1, y), dfs(x + 1, y + 1)); // 非树根，递归左右两边
return f[x][y]; // 返回该节点的结果
}
int main(){
cin >> n;
for(int i = 0; i < n; i ++ ){
for(int j = 0; j <= i; j ++ ){
cin >> a[i][j];
}
}
dfs(0, 0);
cout << f[0][0] << "\n";
return 0;
}
记忆化搜索时间复杂度为: \(n^2\)，n为行数，依旧会超时。
方法三：线性dp
打印一下记忆化搜索结束f数组的值：
20
19 17
15 10 11
5 7 2 1
根据记忆化搜索的过程和f数组不难发现:
f[i][j] = f[i][j] + max(f[i + 1][j], f[i + 1][j + 1])，则此表达式被称之为状态转移方程。
代码如下:
AC代码，展开查看
#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int a[N][N];
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i ++ ){
for(int j = 0; j <= i; j ++ ){
cin >> a[i][j];
}
}
for(int i = n - 2; i >= 0; i -- ){
for(int j = 0; j <= i; j ++ ){
a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
}
}
cout << a[0][0] << endl;
return 0;
}
根据线性dp代码中的
for循环可判断算法时间复杂度为: \(n^2\)，n为行数，不会超时。这个题被卡常了，所以记忆化搜索过不了😂。
思考：
- 可不可以打印出逆推的最大和的路径
逆推的最大和的路径代码如下：
AC代码，展开查看
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], b[N][N];
int p[N][N]; // 定义y坐标增量数组, 每个元素代表y坐标增量
int n;
int main(){
cin >> n;
for(int i = 0; i < n; i ++ ){
for(int j = 0; j <= i; j ++ ){
cin >> a[i][j];
b[i][j] = a[i][j];
}
}
for(int i = n - 2; i >= 0; i -- ){
for(int j = 0; j <= i; j ++ ){
if(a[i + 1][j] > a[i + 1][j + 1]){
a[i][j] += a[i + 1][j];
p[i][j] = 0;
}else{
a[i][j] += a[i + 1][j + 1];
p[i][j] = 1;
}
}
}
for(int i = 0, j = 0; i < n; i ++ ){
if(i != n - 1) cout << b[i][j] << "->";
else cout << b[i][j];
j += p[i][j];
}
cout << "\n";
cout << a[0][0] << endl;
return 0;
}
- 可不可以正着递推？可不可以打印出正推的最大和的路径？
正着推代码如下:
AC代码，展开查看
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N][N];
int n, ans = 0;
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 = 2; i <= n; i ++ ){
for(int j = 1; j <= i; j ++ ){
a[i][j] += max(a[i - 1][j - 1], a[i - 1][j]);
ans = max(a[i][j], ans);
}
}
cout << ans << "\n";
return 0;
}
正着推输出最大和路径:
1 2 3 4 5 p数组
1 7 0
2 3 8 0
3 8 1 0 1
4 2 7 4 4 0
5 4 5 2 6 5 0
AC代码，展开查看
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], b[N][N];
int p[N]; // 定义y坐标增量数组, 索引代表行数，意义是每行的y坐标增量
int n, ans = 0, y; // y记录最大值和链的尾节点的y坐标，x坐标为n
int main(){
cin >> n;
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= i; j ++ ){
cin >> a[i][j];
b[i][j] = a[i][j];
}
}
for(int i = 2; i <= n; i ++ ){
for(int j = 1; j <= i; j ++ ){
a[i][j] += max(a[i - 1][j - 1], a[i - 1][j]);
if(a[i][j] > ans){
y = j;
ans = a[i][j];
}
}
}
// 倒着追溯
for(int i = n, j = y; i >= 1; i -- ){
if(b[i - 1][j - 1] > b[i - 1][j]){ // 左上角 > 右上角
p[i - 1] = 1;
j -= 1;
}
}
for(int i = 1; i <= n; i ++ ){
cout << "p:" << p[i] << " ";
}
cout << "\n";
for(int i = 1, j = 1; i <= n; i ++ ){
if(i != n) cout << b[i][j] << "->";
else cout << b[i][j];
j += p[i];
}
cout << "\n";
cout << ans << "\n";
return 0;
}
本文参考自【董晓算法的个人空间-哔哩哔哩】
海纳百川，有容乃大！如果文章有什么不足之处，还请大神们评论区留言指出，我在此表达感谢🥰！若大家喜欢我的作品，欢迎点赞、收藏、打赏🎉🎉🎉！