动态规划基础（一）引入-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划基础（一）引入。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

$T a l k$ $i s$ $c h e a p$ $,$ $s h o w$ $m e$ $t h e$ $co d e$

数字三角形

题目大意

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

思路

显然不能用用每步最优解决（手玩一下样例就知道）
我们从顶端到底边，当我们走到 $a [x] [y]$ 的时候，是走 $a [x + 1] [y]$ 还是走 $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$ 掉 $3$ 个点，复杂度还是高
所以我们换一种思路
从下往上加，我们从倒数第二行开始向上，就不用考虑循环找最有路径了
所以当我们在每一个 $a [x] [y]$ 的时候，我们只需要让他加上 $a [x + 1] [y]$ 和 $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$ 的特征的文字描述上 $o i w iki$ 上看吧
oiwiki dp文章来源地址https://www.toymoban.com/news/detail-809305.html

到了这里，关于动态规划基础（一）引入的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！