題目：有一個迷宮是一個被稱為“數(shù)字三角形”的n(n不超過200)層迷宮玻孟，這個迷宮的第i層有i個房間，分別編號為1..i鳍征。除去最后一層的房間黍翎，每一個房間都會有一些通往下一層的房間的樓梯，用符號來表示的話蟆技，就是從第i層的編號為j的房間出發(fā)會有兩條路玩敏，一條通向第i+1層的編號為j的房間，另一條會通向第i+1層的編號為j+1的房間质礼，而最后一層的所有房間都只有一條離開迷宮的道路旺聚。這樣的道路都是單向的，也就是說當沿著這些道路前往下一層的房間或者離開迷宮之后眶蕉，沒有辦法再次回到這個房間砰粹。迷宮里同時只會有一個參與者，而在每個參與者進入這個迷宮的時候，每個房間里都會生成一定數(shù)量的獎券碱璃，這些獎券可以在通過迷宮之后兌換各種獎品弄痹。參賽者小Ho的起點是在第1層的編號為1的房間，現(xiàn)在小Ho悄悄向其他參與者弄清楚了每個房間里的獎券數(shù)量嵌器，希望小Hi幫他計算出他最多能獲得多少獎券肛真。
如圖 藍色箭頭所指即為迷宮的最佳路線
方法一：暴力 ×（時間消耗為2的n次方倍）
方法二：DFS √
DFS還要進行一次優(yōu)化：
由圖可知當走到第三排的時候，實際上可以明確對于上一次的2條線路的最大值爽航。
為了進行這樣的優(yōu)化蚓让，我們需要記錄一個值best(i, j)——當前搜索過的路徑中到達第i層第j個房間時最多能獲取多少獎券，然后在每次進入一個房間的時候讥珍，都檢查當前的sum與best(i, j)的大小關系历极，如果sum小于等于best(i, j)的話，就沒有必要繼續(xù)搜索了呢衷佃。比如在之前的例子中趟卸，當通過綠色路徑到達第3層第2個房間的時候，best(i, j)=10氏义，而sum = 8锄列，所以是沒有必要繼續(xù)往下搜索的∶偕蓿”
然后就可以得出一個公式右蕊。所以可以直接用來寫了。
#include<cstdio>
#include<algorithm>
using namespace std;
int reward[105][105];
int best[105][105];
int main()
{
int n, i, j, sum=0, maxx=-1;
scanf("%d", &n);
for(i=0; i<n; i++)
{
for(j=0; j<=i; j++)
{
scanf("%d", &reward[i][j]);
}
}
for(i=0; i<n; i++)
{
for(j=0; j<=i; j++)
{
if(!i && !j) best[i][j]=reward[i][j];
else if(!j) best[i][j]=best[i-1][j]+reward[i][j];
else if(i==j) best[i][j]=best[i-1][j-1]+reward[i][j];
else best[i][j]=max(best[i-1][j-1],best[i-1][j])+reward[i][j];
}
}
for(i=0; i<n; i++)
{
if(best[n-1][i]>maxx) maxx=best[n-1][i];
}
printf("%d\n", maxx);
return 0;
}
