題目：

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

這道題是數(shù)字三角形問題嘱能，可以用動態(tài)規(guī)劃的方法解決吝梅。
從每一個點(diǎn)（最后一行除外）到下一行的走法有兩種，假設(shè)該點(diǎn)為第i行第j列惹骂，則可以走到第i+1行第j列或者第i+1行第j+1列苏携。如果暴力的話肯定過不了。但是我們可以發(fā)現(xiàn)第i行第j列到底端的數(shù)字之和取決于當(dāng)前第i行第j列的值以及第i+1行第j列到底端的數(shù)字之和和第i+1行第j+1列到底端的數(shù)字之和对粪。因此我們可以得到一個狀態(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個數(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ù)字三角形 動態(tài)規(guī)劃;
    for (int j = 1;j <= n;++j) {//從最后一層開始向上遞推;
        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;
}