一、问题描述

从数塔顶层出发，每个结点可以选择向左走或向右走，要求一直走到塔底，使得走过的路径上的数值和最大。

如上图所示的数塔，最大路径和为86，经过的路径从塔顶到塔底为13，8，26，15，24。

二、问题分析

要求的最大值可以从地形开始也可以从上面开始

动态规划函数为：

resultTower[i][j] = tower[i][j] + Math.max(tower[i + 1][j],tower[i + 1][j + 1]);

 

边界值resultTower[heigh - 1][j] = tower[heigh - 1][j];

/*Author::若尘*/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int dp[1002][1002];int main() {  int t;  scanf("%d", &t);  int count = 1;  while (t--) {    memset(dp, 0, sizeof(dp));    int n, m;    scanf("%d%d", &n, &m);    for (int i = 1; i <= n; i++) {      for (int j = 1; j <= m; j++) {        scanf("%d", &dp[i][j]);      }    }    for (int i = 1; i <= n; i++) {      for (int j = 1; j <= m; j++) {        dp[i][j] += max(dp[i-1][j], dp[i][j-1]);      }    }    printf("Scenario #%d:\n", count++);    printf("%d\n\n", dp[n][m]);  }}