度度熊是一只喜欢探险的熊，一次偶然落进了一个m*n矩阵的迷宫，该迷宫只能从矩阵左上角第一个方格开始走，只有走到右上角的第一个格子才算走出迷宫，每一次只能走一格，且只能向上向下向右走以前没有走过的格子，每一个格子中都有一些金币（或正或负，有可能遇到强盗拦路抢劫， 度度熊身上金币可以为负，需要给强盗写欠条），度度熊刚开始时身上金币数为0，问度度熊走出迷宫时候身上最多有多少金币？

Case #1:

18

Case #2:

4

非常简单的dp，首先分析状态，第一列的状态是确定的，只能从上一气走到下。那么从第二列往后呢？
不难发现，第二列往后的位置ans[i][j]的值有3种情况，从左，下，上三个方向分别到达该点。我们在这里定义两个dp[i][j]一个来保存从上走到下，另一个保存从下走到上的最大值，
在这两个dp中分别更新从前一列走还是从上（或下）最优，然后取个max就行了！
代码如下：

 #include <bits/stdc++.h>

 using namespace std;

 int t,n,m,mapp[][],dp1[][],dp2[][],ans[][];

 int main()

 {

     //freopen("de.txt","r",stdin);

     scanf("%d",&t);

     int casee=;

     while (t--)

     {

         scanf("%d%d",&n,&m);

         printf("Case #%d:\n",++casee);

         for (int i=;i<=n;++i)

         {

             for (int j=;j<=m;++j)

             scanf("%d",&mapp[i][j]);

         }

         ans[][]=mapp[][];

         for (int i=;i<=n;++i)

         ans[i][]=ans[i-][]+mapp[i][];

         for (int j=;j<=m;++j)

         {

             dp1[][j]=ans[][j-]+mapp[][j];

             for (int i=;i<=n;++i)

             dp1[i][j]=max(dp1[i-][j],ans[i][j-])+mapp[i][j];

             dp2[n][j]=ans[n][j-]+mapp[n][j];

             for (int i=n-;i>=;--i)

             dp2[i][j]=max(dp2[i+][j],ans[i][j-])+mapp[i][j];

             for (int i=;i<=n;++i)

             ans[i][j]=max(dp1[i][j],dp2[i][j]);

         }

         printf("%d\n",ans[][m]);

         /*

         for (int i=1;i<=n;++i)

         {

             for (int j=1;j<=m;++j)

             printf("%d ",ans[i][j]);

             printf("\n");

         }*/

     }

     return ;

 }