动态规划 数字三角形

题目：有一个迷宫是一个被称为“数字三角形”的n(n不超过200)层迷宫，这个迷宫的第i层有i个房间，分别编号为1..i。除去最后一层的房间，每一个房间都会有一些通往下一层的房间的楼梯，用符号来表示的话，就是从第i层的编号为j的房间出发会有两条路，一条通向第i+1层的编号为j的房间，另一条会通向第i+1层的编号为j+1的房间，而最后一层的所有房间都只有一条离开迷宫的道路。这样的道路都是单向的，也就是说当沿着这些道路前往下一层的房间或者离开迷宫之后，没有办法再次回到这个房间。迷宫里同时只会有一个参与者，而在每个参与者进入这个迷宫的时候，每个房间里都会生成一定数量的奖券，这些奖券可以在通过迷宫之后兑换各种奖品。参赛者小Ho的起点是在第1层的编号为1的房间，现在小Ho悄悄向其他参与者弄清楚了每个房间里的奖券数量，希望小Hi帮他计算出他最多能获得多少奖券。

迷宫示意图

如图 蓝色箭头所指即为迷宫的最佳路线

方法一：暴力 ×（时间消耗为2的n次方倍）
方法二：DFS √

DFS还要进行一次优化：
由图可知当走到第三排的时候，实际上可以明确对于上一次的2条线路的最大值。
为了进行这样的优化，我们需要记录一个值best(i, j)——当前搜索过的路径中到达第i层第j个房间时最多能获取多少奖券，然后在每次进入一个房间的时候，都检查当前的sum与best(i, j)的大小关系，如果sum小于等于best(i, j)的话，就没有必要继续搜索了呢。比如在之前的例子中，当通过绿色路径到达第3层第2个房间的时候，best(i, j)=10，而sum = 8，所以是没有必要继续往下搜索的。”

总结公式

然后就可以得出一个公式。所以可以直接用来写了。

#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;
}