題目鏈接
原題鏈接
題目描述
給定一個如下圖所示的數字三角形，從頂部出發，在每一結點可以選擇移動至其左下方的結點或移動至其右下方的結點，一直走到底層，要求找出一條路徑，使路徑上的數字的和最大，
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
輸入格式
第一行包含整數 n，表示數字三角形的層數，
接下來 n 行，每行包含若干整數，其中第 i 行表示數字三角形第 i 層包含的整數，
輸出格式
輸出一個整數，表示最大的路徑數字和，
資料范圍
1≤n≤500,
?10000≤三角形中的整數≤10000
輸入樣例：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
輸出樣例：
30
難度：簡單
時/空限制：1s / 64MB
來源：模板題, usaco training 1.6
演算法標簽
動態規劃、線性DP
思路
代碼
點擊查看代碼
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 510;
const int 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];
//初始化f[][],防止越界
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]+a[i][j] , 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/499865.html
標籤：其他
上一篇：B樹詳解
下一篇：LeetCode - 回文數