题目1：数字三角形

?

【题目解读】

最基础的动态规划，提示中对于可以使用动态规划的基本条件说明，感觉非常好：

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

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

【编写细节】

DP最难的是边界处理部分，一般都是

（1）best[0][0] 单独处理，n=1 时单独处理；

（2）本题中，三角形最左侧一列、最右侧一斜列，需要单独处理。

【AC代码】

?

#include
  
   
#include
   
     #include
    
      int reward[101][101]; long best[101][101]; long max(long a, long b) { if(a>b) return a; else return b; } int main() { int n; scanf(%d, &n); memset(reward, 0, sizeof(reward)); memset(best, 0, sizeof(best)); for(int i=0; i
     
      
?