數(shù)字金字塔

Description

考慮在下面被顯示的數(shù)字金字塔。

寫一個程序來計算從最高點開始在底部任意處結(jié)束的路徑經(jīng)過數(shù)字的和的最大。

每一步可以走到左下方的點也可以到達(dá)右下方的點。

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

在上面的樣例中,從7 到 3 到 8 到 7 到 5 的路徑產(chǎn)生了最大和:30

Input

第一個行包含 R(1<= R<=1000) ,表示行的數(shù)目。

后面每行為這個數(shù)字金字塔特定行包含的整數(shù)。

所有的被供應(yīng)的整數(shù)是非負(fù)的且不大于100。

Output

單獨的一行包含那個可能得到的最大的和。

Sample Input

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

Sample Output

30

解題思路：

這道題用遞推的方法來做，應(yīng)為本行的結(jié)果只和下一層有關(guān)系，所以可以用一維數(shù)組倒著遞推算出結(jié)果。

狀態(tài)轉(zhuǎn)移方程：

st[j]=max(st[j],st[j+1])+a[i][j];

#include<cstdio> #include<iostream> using namespace std; int st[1001],a[1001][1001],n; int main() {scanf("%d",&n);for (int i=1;i<=n;i++)for (int j=1;j<=i;j++)scanf("%d",&a[i][j]);//輸入for (int i=n;i>=1;i--)for (int j=1;j<=i;j++)st[j]=max(st[j],st[j+1])+a[i][j];//遞推printf("%d",st[1]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【动态规划】数字金字塔的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。