动态规划基础(一)引入

发布时间:2024年01月20日

T a l k Talk Talk i s is is c h e a p cheap cheap , , , s h o w show show m e me me t h e the the c o d e code code

数字三角形

题目大意

给定数字金字塔,每个单位有自己的权值,问从顶端出发,到底端任意一点的所有路径中,经过的权值总和最大的路径,输出权值总和的最大

思路

显然不能用用每步最优解决(手玩一下样例就知道)
我们从顶端到底边,当我们走到 a [ x ] [ y ] a[x][y] a[x][y]的时候 ,是走 a [ x + 1 ] [ y ] a[x+1][y] a[x+1][y]还是走 a [ x + 1 ] [ y + 1 ] a[x+1][y+1] a[x+1][y+1]取决于,从底边到这两点的两条最优路径哪一个大,所以我们需要用循环先把这两条最优路径迭代出来。
根据这个思路写出以下代码

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int a[1005][1005];//金字塔
int dp[1005][1005];//记录路径值
int n;

int result(int x, int y) {
    if (x == n)return dp[x][y] = a[x][y];
    dp[x][y] = max(result(x + 1, y), result(x + 1, y + 1)) + a[x][y];
    return dp[x][y];
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= i;j++)
            cin >> a[i][j];
    cout << result(1, 1);
    return 0;
}

但是仍然会 T T T 3 3 3个点,复杂度还是高
所以我们换一种思路
从下往上加,我们从倒数第二行开始向上,就不用考虑循环找最有路径了
所以当我们在每一个 a [ x ] [ y ] a[x][y] a[x][y]的时候,我们只需要让他加上 a [ x + 1 ] [ y ] a[x+1][y] a[x+1][y] a [ x + 1 ] [ y + 1 ] a[x+1][y+1] a[x+1][y+1]中较大的一个,更新权值就行了

ACcode

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int a[1005][1005];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;cin >> t;
    for (int i = 1;i <= t;i++) 
        for (int j = 1;j <= i;j++) 
            cin >> a[i][j];
    for (int i = t-1;i >= 1;i--) {
        for (int j = 1;j <= i;j++) {
            a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
        }
    }
    cout << a[1][1];
    return 0;
}

具体有一些对于 d p dp dp的特征的文字描述上 o i w i k i oiwiki oiwiki上看吧
oiwiki dp

文章来源:https://blog.csdn.net/weixin_70831807/article/details/135717374
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。