題目：

時(shí)間限制:10000ms
單點(diǎn)時(shí)限:1000ms
內(nèi)存限制:256MB
問(wèn)題描述
小Hi和小Ho在經(jīng)歷了螃蟹先生的任務(wù)之后被獎(jiǎng)勵(lì)了一次出國(guó)旅游的機(jī)會(huì)，于是他們來(lái)到了大洋彼岸的美國(guó)。美國(guó)人民的生活非常有意思，經(jīng)常會(huì)有形形色色、奇奇怪怪的活動(dòng)舉辦，這不，小Hi和小Ho剛剛下飛機(jī)，就趕上了當(dāng)?shù)氐拿詫m節(jié)活動(dòng)。迷宮節(jié)里展覽出來(lái)的迷宮都特別的有意思，但是小Ho卻相中了一個(gè)其實(shí)并不怎么像迷宮的迷宮——因?yàn)檫@個(gè)迷宮的獎(jiǎng)勵(lì)非常豐富~
于是小Ho找到了小Hi，讓小Hi幫助他獲取盡可能多的獎(jiǎng)品，小Hi把手一伸道：“迷宮的介紹拿來(lái)！”
小Ho選擇的迷宮是一個(gè)被稱(chēng)為“數(shù)字三角形”的n(n不超過(guò)200)層迷宮，這個(gè)迷宮的第i層有i個(gè)房間，分別編號(hào)為1..i。除去最后一層的房間，每一個(gè)房間都會(huì)有一些通往下一層的房間的樓梯，用符號(hào)來(lái)表示的話(huà)，就是從第i層的編號(hào)為j的房間出發(fā)會(huì)有兩條路，一條通向第i+1層的編號(hào)為j的房間，另一條會(huì)通向第i+1層的編號(hào)為j+1的房間，而最后一層的所有房間都只有一條離開(kāi)迷宮的道路。這樣的道路都是單向的，也就是說(shuō)當(dāng)沿著這些道路前往下一層的房間或者離開(kāi)迷宮之后，小Ho沒(méi)有辦法再次回到這個(gè)房間。迷宮里同時(shí)只會(huì)有一個(gè)參與者，而在每個(gè)參與者進(jìn)入這個(gè)迷宮的時(shí)候，每個(gè)房間里都會(huì)生成一定數(shù)量的獎(jiǎng)券，這些獎(jiǎng)券可以在通過(guò)迷宮之后兌換各種獎(jiǎng)品。小Ho的起點(diǎn)在第1層的編號(hào)為1的房間，現(xiàn)在小Ho悄悄向其他參與者弄清楚了每個(gè)房間里的獎(jiǎng)券數(shù)量，希望小Hi幫他計(jì)算出他最多能獲得多少獎(jiǎng)券。
提示一：盲目貪心不可取，搜索計(jì)算太耗時(shí)
提示二：記憶深搜逞神威，寬度優(yōu)先解難題
提示三：總結(jié)歸納提公式，減少冗余是真理
輸入
每個(gè)測(cè)試點(diǎn)（輸入文件）有且僅有一組測(cè)試數(shù)據(jù)。
每組測(cè)試數(shù)據(jù)的第一行為一個(gè)正整數(shù)n,表示這個(gè)迷宮的層數(shù)。
接下來(lái)的n行描述這個(gè)迷宮中每個(gè)房間的獎(jiǎng)券數(shù)，其中第i行的第j個(gè)數(shù)代表著迷宮第i層的編號(hào)為j的房間中的獎(jiǎng)券數(shù)量。
測(cè)試數(shù)據(jù)保證，有100%的數(shù)據(jù)滿(mǎn)足n不超過(guò)100
對(duì)于100%的數(shù)據(jù)，迷宮的層數(shù)n不超過(guò)100
對(duì)于100%的數(shù)據(jù)，每個(gè)房間中的獎(jiǎng)券數(shù)不超過(guò)1000
對(duì)于50%的數(shù)據(jù)，迷宮的層數(shù)不超過(guò)15（小Ho表示2^15才3萬(wàn)多呢，也就是說(shuō)……）
對(duì)于10%的數(shù)據(jù)，迷宮的層數(shù)不超過(guò)1（小Hi很好奇你的邊界情況處理的如何？~）
對(duì)于10%的數(shù)據(jù)，迷宮的構(gòu)造滿(mǎn)足：對(duì)于90%以上的結(jié)點(diǎn)，左邊道路通向的房間中的獎(jiǎng)券數(shù)比右邊道路通向的房間中的獎(jiǎng)券數(shù)要多。
對(duì)于10%的數(shù)據(jù)，迷宮的構(gòu)造滿(mǎn)足：對(duì)于90%以上的結(jié)點(diǎn)，左邊道路通向的房間中的獎(jiǎng)券數(shù)比右邊道路通向的房間中的獎(jiǎng)券數(shù)要少。
輸出
對(duì)于每組測(cè)試數(shù)據(jù)，輸出一個(gè)整數(shù)Ans，表示小Ho可以獲得的最多獎(jiǎng)券數(shù)。
樣例輸入
5
2
6 4
1 2 8
4 0 9 6
6 5 5 3 6
樣例輸出
28

這道題是數(shù)字三角形問(wèn)題，可以用動(dòng)態(tài)規(guī)劃的方法解決。
從每一個(gè)點(diǎn)（最后一行除外）到下一行的走法有兩種，假設(shè)該點(diǎn)為第i行第j列，則可以走到第i+1行第j列或者第i+1行第j+1列。如果暴力的話(huà)肯定過(guò)不了。但是我們可以發(fā)現(xiàn)第i行第j列到底端的數(shù)字之和取決于當(dāng)前第i行第j列的值以及第i+1行第j列到底端的數(shù)字之和和第i+1行第j+1列到底端的數(shù)字之和。因此我們可以得到一個(gè)狀態(tài)轉(zhuǎn)移方程式：
dp[i][j] = num[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
最終的結(jié)果就是dp[1][1].

參考代碼：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100+5;

int mp[N][N];
int dp[N][N];//第i行第j個(gè)數(shù)到底端的數(shù)字之和的最大值;

void input(const int n) {
    for (int i = 1;i <= n;++i) {
        for (int j = 1;j <= i;++j) {
            cin >> mp[i][j];
        }
    }
}

int numtri(const int n) {//數(shù)字三角形 動(dòng)態(tài)規(guī)劃;
    for (int j = 1;j <= n;++j) {//從最后一層開(kāi)始向上遞推;
        dp[n][j] = mp[n][j];
    }

    for (int i = n-1;i >= 1;--i) {
        for (int j = 1;j <= i;++j) {
            dp[i][j] = mp[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
        }
    }

    return dp[1][1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    input(n);

    int ans = numtri(n);
    cout << ans << endl;
    return 0;
}