1220 數(shù)字三角形

?

時(shí)間限制: 1 s 空間限制: 128000 KB 題目等級(jí) : 黃金 Gold 題解 題目描述?Description

如圖所示的數(shù)字三角形，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或得向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。

輸入描述?Input Description

第一行是數(shù)塔層數(shù)N(1<=N<=100)。

第二行起，按數(shù)塔圖形，有一個(gè)或多個(gè)的整數(shù)，表示該層節(jié)點(diǎn)的值，共有N行。

輸出描述?Output Description

輸出最大值。

樣例輸入?Sample Input

5

13

11 8

12 7?26

6 14 15 8

12 7 13 24 11

樣例輸出?Sample Output

86

數(shù)據(jù)范圍及提示?Data Size & Hint 數(shù)字三角形

分類標(biāo)簽?Tags?點(diǎn)此展開(kāi)?

動(dòng)態(tài)規(guī)劃棋盤(pán)型DP 動(dòng)態(tài)規(guī)劃做法： #include
using namespace std;
#include
int f[101][101],a[101][101];
int main()
{
?int n;
?scanf("%d",&n);
?for(int i=1;i<=n;++i)
?? for(int j=1;j<=i;++j)
?? {
??? scanf("%d",&a[i][j]);
?????? f[i][j]=a[i][j];
?? }
?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];
?printf("%d\n",f[1][1]);
?return 0;
} 深度優(yōu)先搜索做法： #include
using namespace std;
#include
#include
int n,f[101][101],a[101][101];
int dfs(int i,int j)
{
?if(i==n) return a[i][j];
?if(f[i][j]!=0) return f[i][j];
?f[i][j]=max(dfs(i+1,j),dfs(i+1,j+1))+a[i][j];
?return f[i][j];
}
int main()
{
?scanf("%d",&n);
?for(int i=1;i<=n;++i)
?? for(int j=1;j<=i;++j)
?? {
?? ?scanf("%d",&a[i][j]);
?? ?
?? }
?if(n==1)//處理n是1層的時(shí)候，深搜就不必進(jìn)行了
?{
??printf("%d\n",a[1][1]);
??return 0;
?}
?int i=1,j=1;
?f[1][1]=max(dfs(i+1,j),dfs(i+1,j+1))+a[1][1];
?printf("%d\n",f[1][1]);
?return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/c1299401227/p/5370731.html

總結(jié)

以上是生活随笔為你收集整理的89.数字三角形的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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