数字三角形（简单DP）

问题描述

小Hi和小Ho在经历了螃蟹先生的任务之后被奖励了一次出国旅游的机会，于是他们来到了大洋彼岸的美国。美国人民的生活非常有意思，经常会有形形色色、奇奇怪怪的活动举办，这不，小Hi和小Ho刚刚下飞机，就赶上了当地的迷宫节活动。迷宫节里展览出来的迷宫都特别的有意思，但是小Ho却相中了一个其实并不怎么像迷宫的迷宫——因为这个迷宫的奖励非常丰富~

于是小Ho找到了小Hi，让小Hi帮助他获取尽可能多的奖品，小Hi把手一伸道：“迷宫的介绍拿来！”

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

提示一：盲目贪心不可取，搜索计算太耗时

提示二：记忆深搜逞神威，宽度优先解难题

提示三：总结归纳提公式，减少冗余是真理

“我们可以来分分情况，我们要搜索所有的路径，然后依次计算每条路径的收益，这是我们现在的问题模型是不是？”小Hi问道。

小Ho点头：“仔细分析这个迷宫的话，我们有两种搜索方法，一种是深度优先搜索，就像这幅图画的一样，我们先试着顺着每个房间的第一条路一直下去，一直走到最后一层，然后返回至倒数第二层，选择第二条路走到最后一个房间，然后返回到倒数第三层，选择第二条路走到倒数第二层，然后选择第一条路走到最后一层……期间维护已经走过的房间的奖券之和sum，然后每次到达最后一层的房间的时候将sum与全局最优解ans进行比较，如果sum>ans的话就用sum替换ans。这样在所有路径都计算过一遍之后，Ans中存储的就是我们要的答案了~~而第二种……”

“先别说第二种，我们来看看这种方法有什么办法优化么~”小Hi打断了小Ho的喋喋不休。

“哦，但是该怎么优化呢？”小Ho问道。

“老规矩，我们来看看这个过程中有什么冗余计算~”小Hi还是那一套说辞，也不担心小Ho听了这么多遍听厌：“看这张图，当你枚举到绿色的‘-》右-》左’这样一条路径的时候，是不是发现它和红色的‘-》左-》右’这条路径一样都到达了第三层的第二个房间？”

“是的！”

“在你枚举到绿色路径的时候，是不是红色路径已经被枚举过了？”小Hi接着问道。

“没错！“

“那么你看，绿色路径的奖券和是8，红色路径的奖券和是10，而你们都处于了相同的结点——第3层的第2个房间上，这时候无论你绿色路径接下来延续出什么样的路径，我将从第3层第2个房间开始的这一段连在红色路径之后的话，奖券和都会要比绿色路径要多？”小Hi继续问。

“嗯……对的~”

“而这些路径中的最优值都肯定不超过Ans，不然Ans就会在当时变得和它们一样，这不就说明了绿色路径无论接下来如何走，都不可能对Ans造成任何变化，那我们是不是完全可以不进行接下来的计算了呢？”小Hi做出了最后的结论。

“是的……为了进行这样的优化，我们需要记录一个值best(i, j)——当前搜索过的路径中到达第i层第j个房间时最多能获取多少奖券，然后在每次进入一个房间的时候，都检查当前的sum与best(i, j)的大小关系，如果sum小于等于best(i, j)的话，就没有必要继续搜索了呢。比如在之前的例子中，当通过绿色路径到达第3层第2个房间的时候，best(i, j)=10，而sum = 8，所以是没有必要继续往下搜索的。”聪明的小Ho很快就将这个算法总结了出来。

“而这种做法，由于是通过之前的记忆来避免不必要的搜索，所以被大家称为‘记忆化搜索’”小Ho笑道：“这样，只要不是那种非常坏的卡你的情况——比如第i层第j个房间的奖券数是j这种，都能够在O(n^2)的复杂度通过了呢。”

“而如果我先右再左呢？”小Ho不死心。

“那我就第i层第j个房间的奖券数是i-j”小Ho邪恶的笑着：“其实你不用纠结这个，你只要随机一下就能够保证几乎所有情况都是O(n^2)的时间复杂度，或者说平均复杂度是O(n^2)，但是你的最坏情况复杂度肯定是降不下去的，所以还是老老实实想想别的方法吧~比如之前你想说的第二种方法？”

“与深度优先搜索相对应的自然就是宽度优先遍历啦~如果我们用<i, j, k>表示到达第i行的第j个房间，当前获得的奖券数为k这样一个状态，rewards(i, j)表示第i层第j个房间中的奖券数，那么遍历方式就是利用一个队列，先将ə, 1, rewards(1, 1)>这个状态放入队列中。然后每次取出队首<i, j, k>，如果i==n，就用k更新Ans，不然就将它代表的房间所能到达的两个房间的状态<i + 1, j, k + rewards(i + 1, j)>和<i + 1, j + 1, k + rewards(i + 1, j + 1)>放入队尾，直到整个队列清空，这时候Ans就是我们要的答案。”小Ho缓缓道来。

“那你觉得这个地方又有什么可以优化的呢？”

“本来我还没想到，但是你说了之前深度优先搜索的问题之后我就有点思路了，你看状态(2, 1, 8)和状态(2, 2, 6)在处理时一个会拓展出(3, 2, 10)这个状态，而另一个会拓展出(3, 2, 8)这个状态，但是就像我们之前的分析那样(3, 2, 8)这个状态是没有什么用的，它之后无论怎么走，换成(3, 2, 10)按它一样的走法肯定获得的奖券数要更多。”小Ho触类旁通，一下就找到了问题所在：“所以我可以像深度优先搜索那样用一个best(i, j)记录当前搜索过的路径中到达第i层第j个房间时最多能获取多少奖券，然后在一个状态(i, j, k)想要入队的时候，判断k与best(i, j)的大小，如果k小于等于best(i, j)就没有必要进队了~”

“看来你还陷在了死胡同里，你这样在最坏情况复杂度根本没有变化不是？”小Hi无奈道：“你仔细想想，按照宽度优先搜索的顺序，是不是一个状态(i, j, k)在拓展出(i', j', k')的时候，(i', j', k')要么从来没有入队列，要么就仍然在队列里？”

“唔...这个问题看来，基本上就是这样一层一层的顺序出队列的，那还是那个问题，如果我在判断状态(i, j, k)是否应该入队列的时候，发现了k大于best(i, j)，这个时候如果我再去判断一下队列中是否有一个(i, j, k')的状态。如果没有，就将(i, j, k)入队列，不然因为k'大于k，那么就像我们之前分析的那样(i, j, k')这个状态时无用的，不如就用k去替换掉状态(i, j, k')中的k'，这样也会减少运算不是？”

“没错~而且你仔细分析的话，每个房间都只会入队列和出队列一次，这样就保证了平均情况时间复杂度和最坏情况时间复杂度都是O(n^2)哦！~”

“原来是这样，那么现在问题差不多解决了呢！”小Ho高兴道：“赶紧算出来，我好去拿奖品。”

“急什么！你从这之中可学到了什么知识么？”小Hi拦住了急冲冲的小Ho，问道。

“啊？”

“且不说深度优先这样一个最坏情况下仍然有问题的方法，我们来说这个宽度优先搜索，我们能够使用best(i, j)来进行优化，无非是因为这个问题存在这样两个性质。”小Hi道。

“第一便是无论我是通过怎么样的方式到达第i层第j个房间的，我之前做出的选择不会对我之后的选择做出限制与优待。就像如果我规定至少要向右走3次，那么状态就不仅仅是(i, j, k)这样，还要加上一个已经向右走的次数t，那么你觉得还能就直接像我们之前的方法进行计算么？如果到达第i层第j个房间的路上向右走过3次了，那么之后的走法就没有任何限制，不然就仍会有一个至少要向右走一定次数的限制。这样对于两个状态(i, j, k, l)和(i, j, k', l')，我们就不能够直接判断出那个状态是更加好的。

“没错~其实就是best(i, j)有两个关键字进行参考，而这样的话就不是任意两个状态都可以进行比较的了。”小Ho总结道。

“这样的性质被我们称为无后效性，顾名思义，当前的抉择不会对后面抉择产生影响。”

“那第二个性质呢？”

“第二个性质被我们称为重复子问题，在我们之前的例子中，我们将从起点出发到走出迷宫的最优路分解成了两个子问题，其一是从第2层的第1个房间走出迷宫的最优路，其二是从第2层的第2个房间走出迷宫的最优路，只要能算出这两个部分的最优值，我就可以知道从起点出发到走出迷宫的最优路。”小Hi道：”而按照这样的方法，这两个子问题都有一个相同的子问题——从第3层的第2个房间出发走出迷宫的最优路。”

“这就是重复的子问题了，而我们的做法就是，重复的子问题只计算一次！也就是说我们要先计算出从起点到达第3层的第2个房间的最优线路，然后再考虑接下来怎么走~”小Ho感觉自己渐渐的把握到了关键之处。

“对的，所以综合这样两个性质，我们可以考虑用best(i, j)表示从起点出发，走到第i层第j个房间出发最多可以获得的奖券数。”小Hi提出了一个新的定义：“那么我们要求的答案，便是所有best(n, j)中最大的那一个对不对？

“是的，那该如何求这个呢……”小Ho思索着：“第i层第j个房间可以由第i-1层第j个房间和第i-1层第j-1个房间到达，所以best(i, j) = max{best(i - 1, j - 1), best(i - 1, j)} + rewards(i, j)这样么？”

“是的，这个公式便是我们俗称的状态转移方程，你要做的，就是按照这样的顺序，依次计算出每一个房间的best(i, j)，然后在最后统计所有best(n, j)的最大值，就可以得到答案了。”

“这个过程和宽度优先搜索的确很像，但是由于顺序是确定了的，我可以用一个两重循环，外层是i从1到n枚举层数，内层是j从1到i枚举房间编号，就可以直接进行计算了！”小Ho道。

“你这个公式的边界情况还有待考虑嘛，比如j=1的时候就不需要取max了，直接使用best(i - 1, j)计算即可~”小Hi指出了小Ho存在的一个问题。

“哦~那么j=i的时候也有相似的处理是吧。”

“是的呢！所以快去写程序吧~”小Hi笑了笑：“抓紧时间，迷宫节就要结束了哦！”

输入

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第一行为一个正整数n,表示这个迷宫的层数。

接下来的n行描述这个迷宫中每个房间的奖券数，其中第i行的第j个数代表着迷宫第i层的编号为j的房间中的奖券数量。

测试数据保证，有100%的数据满足n不超过100

对于100%的数据，迷宫的层数n不超过100

对于100%的数据，每个房间中的奖券数不超过1000

对于50%的数据，迷宫的层数不超过15（小Ho表示2^15才3万多呢，也就是说……）

对于10%的数据，迷宫的层数不超过1（小Hi很好奇你的边界情况处理的如何？~）

对于10%的数据，迷宫的构造满足：对于90%以上的结点，左边道路通向的房间中的奖券数比右边道路通向的房间中的奖券数要多。

对于10%的数据，迷宫的构造满足：对于90%以上的结点，左边道路通向的房间中的奖券数比右边道路通向的房间中的奖券数要少。

输出

对于每组测试数据，输出一个整数Ans，表示小Ho可以获得的最多奖券数。

Sample Input

Sample Output

 1 /*
 2 问题 第i行有i个数字的数字三角形，从第一行走到末行，每个数字只能向直下和下右走，计算并输出最多奖券数
 3 变量 行数，房间数，奖券数 
 4 抽象问题 从起点位置走到第i行第j个房间，最多的奖券数价值是多少
 5 无后效性 之前作出的选择对后面的选择没有限制和优待 
 6 重复子问题  将从起点出发到走出迷宫的最优路分解成了两个子问题，
 7 其一是从第2层的第1个房间走出迷宫的最优路，
 8 其二是从第2层的第2个房间走出迷宫的最优路，只要能算出这两个部分的最优值，我们就可以知道从起点出发到走出迷宫的最优路。
 9 照这样的方法，这两个子问题都有一个相同的子问题——从第3层的第2个房间出发走出迷宫的最优路。
10 
11 状态 best[i][j]表示从起点出发到达第i行第j个房间，能够获得的最多奖券数
12 状态转移 best[i][j]=max(best[i-1][j],best[i-1][j-1]) + map[i][j];
13 边界确定 j=1时，best[i][j]=best[i-1][j] + map[i][j];
14        j=i时，best[i][j]=best[i-1][j-1] + map[i][j]; 
15 */
16 #include<stdio.h>
17 /*const int N=110;GCC编译器中const定义的N会报错，因为在C语言中，const不是一个真真正正的常量，其代表的含义仅仅是只读。
18 使用const声明的对象是一个运行时对象，无法使用其作为某个量的初值、数组的长度、case的值或在类型的情形中使用。需要替换成
19 下面的define定义*/ 
20 #define N 100
21 int map[N][N];
22 int best[N][N];
23 int max(int x,int y){
24     return x>y?x:y;
25 }
26 int main()
27 {
28     int n,i,j;
29     while(scanf("%d",&n) != EOF)
30     {
31         for(i=1;i<=n;i++)
32             for(j=1;j<=i;j++)
33                  scanf("%d",&map[i][j]);
34         best[1][1]=map[1][1];
35         for(i=2;i<=n;i++){
36             for(j=1;j<=i;j++){
37                 if(j==1)
38                 best[i][j]=best[i-1][j]+map[i][j];
39                 else if(j==i)
40                 best[i][j]=best[i-1][j-1]+map[i][j];
41                 else 
42                 best[i][j]=max(best[i-1][j],best[i-1][j-1]) + map[i][j];
43             }
44         }
45         int ans=-1;
46         for(i=1;i<=n;i++){
47             if(best[n][i] > ans)
48                 ans=best[n][i];
49         }
50         printf("%d
",ans);
51     }
52     return 0;
53  }