c++ 动态规划(数塔)

释放双眼,带上耳机,听听看~!

c++ 动态规划(dp)

题目描述

观察下面的数塔。写一个程序查找从最高点到底部任意位置结束的路径,使路径经过数字的和最大。
每一步可以从当前点走到左下角的点,也可以到达右下角的点。

输入

5
13
11 8
12 7 26
6 14 15 8 
12 7 13 24 11

输出

86

AC代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
int dp[MAXN][MAXN],a[MAXN][MAXN];
int max(int a,int b)//max函数求两个数字之间的最大值
{
    return a>b?a:b;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1;i <= n;i ++)//输入
    {
        for (int j = 1;j <= i;j ++)
        {
            cin >> a[i][j];
        }
    }
    dp[1][1] = a[1][1];//把起点直接放在dp[]里面
    for (int i = 2;i <= n;i ++)
    {
        for (int j = 1;j <= i;j ++)
        {
            dp[i][j] = max(dp[i - 1][j - 1],dp[i - 1][j]) + a[i][j];//dp公式,原理是先走一步,然后扫描这个点的上一层的邻接点看看哪个点的dp值最大,然后用最大值加上他本身
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i ++)
    {
        ans = max(ans,dp[n][i]);//ans的作用是在最底部的元素中找一个最大的dp,输出
    }
    cout << ans << endl;
    return 0;
}

给TA打赏
共{{data.count}}人
人已打赏
随笔日记

深入了解数据校验:Java Bean Validation 2.0(JSR380)

2020-11-9 6:02:15

随笔日记

中基协发布第二十九批81家疑似失联私募机构名单

2020-11-9 6:02:17

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索