題目描述

觀察下面的數字金字塔。

寫一個程序來查找從最高點到底部任意處結束的路徑，使路徑經過數字的和最大。每一步可以走到左下方的點也可以到達右下方的點。

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

在上面的樣例中，從7 到 3 到 8 到 7 到 5 的路徑產生了最大

輸入輸出格式

輸入格式：

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

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

所有的被供應的整數是非負的且不大于100。

輸出格式：

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

輸入輸出樣例

輸入樣例#1：

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

輸出樣例#1：

30

源代碼

#include<iostream> #include<algorithm> using namespace std; int dp[1005][1005]={0}; int num[1005][1005]; int main() {int r;int i,j;cin>>r;for(i=1;i<=r;i++)for(j=1;j<=i;j++){cin>>num[i][j];dp[i][j]=num[i][j];}for(i=r-1;i>0;i--)//從下向上找，直接輸出dp[1][1]即可，可以省去一個循環查找最大值for(j=1;j<=i;j++)dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);//當前值=左下值、右下值中的最大值cout<<dp[1][1]<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的数字三角形（洛谷-P1216）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。