动态规划

动态规划

动态规划(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为行数,不会超时。这个题被卡常了,所以记忆化搜索过不了😂。

思考:

  1. 可不可以打印出逆推的最大和的路径

逆推的最大和的路径代码如下:

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;
}
  1. 可不可以正着递推?可不可以打印出正推的最大和的路径?

正着推代码如下:

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;
}

本文参考自【董晓算法的个人空间-哔哩哔哩】

海纳百川,有容乃大!如果文章有什么不足之处,还请大神们评论区留言指出,我在此表达感谢🥰!若大家喜欢我的作品,欢迎点赞、收藏、打赏🎉🎉🎉!

热门相关:绍宋   试婚100天:夜少,轻轻宠   余生皆是喜欢你   你好,墨先生   这个大佬有点苟