历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 898. 【算法基础课】数字三角形（线性DP）原题链接简单

作者：

incra , 2022-09-25 07:37:29 , 所有人可见 , 阅读 5398

107

10

<—点个赞吧QwQ

宣传一下算法基础课整理

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入格式

第一行包含整数 $n$，表示数字三角形的层数。

接下来 $n$ 行，每行包含若干整数，其中第 $i$ 行表示数字三角形第 $i$ 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

$1 \le n \le 500$,
$-10000 \le 三角形中的整数 \le 10000$

输入样例：

输出样例：

思路1

这题有两种写法，这里都讲一下。
闫氏$DP$分析法：
状态表示：$f_{i,j}$

集合：从$(1,1)$到$(i,j)$所有方案的集合
属性：$Max$

状态计算：

这个点可以由$(i-1,j)$走过来，即$f_{i-1,j}+a_{i,j}$
这个点也可以由$(i-1,j-1)$走过来，即$f_{i-1,j-1}+a_{i,j}$
所以状态转移方程就是$f_{i,j}=\max\lbrace f_{i-1,j},f_{i-1,j-1}\rbrace+a_{i,j}$

答案：

根据定义，这里答案就是最下面那一层的和，即$\underset{1\le i\le n}{\max}\lbrace f_{n,i}\rbrace$

代码1

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510,INF = 1e9;
int n;
int a[N][N],f[N][N];
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 = 0;i <= n;i++) {
        for (int j = 0;j <= i + 1;j++) {
            f[i][j] = -INF;
        }
    }
    f[1][1] = a[1][1];
    for (int i = 2;i <= n;i++) {
        for (int j = 1;j <= i;j++) {
            f[i][j] = max (f[i - 1][j - 1],f[i - 1][j]) + a[i][j];
        }
    }
    int ans = -INF;
    for (int i = 1;i <= n;i++) ans = max (ans,f[n][i]);
    cout << ans << endl;
    return 0;
}

思路2

闫氏$DP$分析法：
状态表示：$f_{i,j}$

集合：从$(i,j)$到最后一层的所有方案
属性：$Max$

状态计算

这条路径可以从$(i+1,j)$走上来，即$f_{i+1,j}+a_{i,j}$
也可以从$(i+1,j+1)$走上来，即$f_{i+1,j+1}+a_{i,j}$
所以状态转移方程就是$f_{i,j}=max\lbrace f_{i+1,j},f_{i+1,j+1} \rbrace +a_{i,j}$

答案：

根据定义，答案就是$f_{1,1}$

代码2

#include <iostream>
using namespace std;
const int N = 510;
int n;
int a[N][N];
int f[N][N];
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 = 1;i <= n;i++) f[n][i] = a[n][i];
    for (int i = n - 1;i >= 1;i--) {
        for (int j = 1;j <= i;j++) {
            f[i][j] = max (f[i + 1][j],f[i + 1][j + 1]) + a[i][j];
        }
    }
    cout << f[1][1] << endl;
    return 0;
}

36 评论

超人不会飞_8 8个月前

为什么用memset将f数组全部初始化为-1e9就过不了呢？

超人不会飞_8 8个月前

过不了全部样例

incra 8个月前

你可以学一下memset的原理，他不是那么简单的问题

code002 4个月前

memset 用0xcf

早上起来胡辣汤就着算法题会不会更下饭点 4个月前

可以的

#include<bits/stdc++.h>

using namespace std;


const int N = 520;

int n;
int f[N][N], a[N][N];

int main()
{
    cin >> n;
    //防止边界问题，从1开始赋值
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= i; j ++ )
            cin >> a[i][j];

    memset(f, -0x3f3f3f3f, sizeof f);

    //赋初值，第一个状态已经知晓
    f[1][1] = a[1][1];
    //所以从2开始遍历
    for(int i = 2; i <= n; i ++ )
        for(int j = 1; j <= i; j ++ )
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);

    int res = -0x3f3f3f3f;
    for(int i = 1; i <= n; i ++ )   res = max(res,f[n][i]);

    cout << res;
}

愚公_0 19天前

memset(f,-0x3f,sizeof f);
能过

Gpd001 9个月前

这个能不能用滚动数组优化？

Gpd001 9个月前

尝试ing

Gpd001 9个月前

两层成了，但一维不会了

#include <bits/stdc++.h>

using namespace std;
const int N = 520;
int n, a = 1, ans = -0x3f3f3f3f;
int d[2][N];
int main(){
    scanf ("%d", &n);
    memset(d, -0x3f, sizeof(d));
    for (int i = 1;i <= n;i ++, a = !a){
        for (int j = 1;j <= i;j ++)
            scanf ("%d", &d[a][j]);
        for (int j = 1;i - 1 && j <= i;j ++)
            d[a][j] += max(d[!a][j], d[!a][j - 1]);
    }
    a = n % 2;
    for (int i = 1;i <= n;i ++)
        ans = max(ans, d[a][i]);
    cout << ans;
    return 0;
}

Gpd001 9个月前回复了 Gpd001 的评论

比Y总的快10ms ~~虽然没什么卵用~~

incra 9个月前回复了 Gpd001 的评论

### 一维代码1：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510,INF = 1e9;
int n;
int a[N][N],f[N];
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 = 0;i <= n;i++) f[i] = -INF;
    f[1] = a[1][1];
    for (int i = 2;i <= n;i++) {
        for (int j = i;j >= 1;j--) {
            f[j] = max (f[j - 1],f[j]) + a[i][j];
        }
    }
    int ans = -INF;
    for (int i = 1;i <= n;i++) ans = max (ans,f[i]);
    cout << ans << endl;
    return 0;
}

### 一维代码2：

#include <iostream>
using namespace std;
const int N = 510;
int n;
int a[N][N];
int f[N];
int main () {
    ios :: sync_with_stdio (false),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];
    }
    for (int i = 1;i <= n;i++) f[i] = a[n][i];
    for (int i = n - 1;i >= 1;i--) {
        for (int j = 1;j <= i;j++) {
            f[j] = max (f[j],f[j + 1]) + a[i][j];
        }
        // for (int j = 1;j <= i;j++) cout << f[j] << ' ';
        // cout << endl;
    }
    cout << f[1] << endl;
    return 0;
}

Gpd001 9个月前回复了 incra 的评论

# 强!!!

Gpd001 9个月前回复了 incra 的评论

从讨论里又翻出来一个
https://www.acwing.com/problem/content/discussion/content/5537/

2123899646@qq.com 8个月前回复了 Gpd001 的评论

小丑，根本就是错的，结果都不对

2123899646@qq.com 8个月前回复了 incra 的评论

小丑，根本就是错的，输出不是正确答案

incra 8个月前回复了 2123899646@qq.com 的评论

操，我有空改一下

incra 8个月前回复了 2123899646@qq.com 的评论

但是这个代码能过啊？

incra 8个月前回复了 2123899646@qq.com 的评论

两个代码都能AC

Gpd001 8个月前回复了 2123899646@qq.com 的评论

错误数据？
# 提交工单

incra 8个月前回复了 Gpd001 的评论

????

incra 8个月前回复了 incra 的评论

什么意思啊

Gpd001 8个月前回复了 incra 的评论

从这里找到错误数据，然后我拿去提交工单（嘿嘿）

incra 8个月前回复了 Gpd001 的评论

什么数据，给我看看

incra 8个月前回复了 Gpd001 的评论

你怎么知道你的数据是对的

Gpd001 8个月前回复了 incra 的评论

2123899646@qq.com 不是这个人说跑不出正确结果吗？

incra 8个月前回复了 Gpd001 的评论

科幻_恩荣 2023-08-05 11:42

写得太棒了

泡椒_ 7个月前

怎样存储路径呀？

incra 7个月前

记录从哪里转以来的即可

泡椒_ 7个月前回复了 incra 的评论

已经搞明白了，感谢

超人不会飞_8 8个月前

#include[HTML_REMOVED]
using namespace std;
const int N=510;
int a[N][N],f[N][N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i)
for(int j=1;j<=i;j)
scanf(“%d”,&a[i][j]);
memset(f,-1e9,sizeof f);
f[1][1]=a[1][1];
for(int i=2;i<=n;i)
for(int j=1;j<=i;j)
{
f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
}
int ans=-1e9;
for(int j=1;j<=n;j++)
ans=max(ans,f[n][j]);
cout<<ans<<endl;
return 0;
}