题目：http://acm.hdu.edu.cn/showproblem.php?pid=2391
题目大意：给定一个矩阵，从左上角第一个元素开始到右下最后一个元素，寻找一条路线，使得路线经过的矩阵元素之和加起来最大，路线的方向可以向右→，可以向下↓，也可以斜向右下(只有在矩阵元素有负数的时候，斜向右下的方向才有必要考虑，本题可以考虑这一点，但是没有必要)
有两种方法可以求解
方法一：动态规划
循环地针对矩阵每一个元素，求出，在目前情况下从起点到当前点的所有路线中，使得元素的最大和，并以这个最大值来更新当前位置的数值，待所有元素值更新结束之后，最后一个元素的值就是所求的最大值.
以题目中的测试数据为例，动态规划过程如下(从左向右，从上往下)
最后结果是42.
C++代码如下
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std; int main()
{
int T,r,c;
cin >> T;//测试的组数
for(int k=1;k<=T;k++)
{
cin >> r >> c;//矩阵的行数r和列数c
int ** a = new int* [r+1];//处于代码需要，数组大小比矩阵多一行一列，第一行第一列一直是0. for(int i=0;i<=r;i++)//从0到r行
{
a[i] = new int[c+1];
for(int j=0;j<=c;j++)//从0到c列
a[i][j] = 0;//所有元素都初始化为0
} for(int i=1;i<=r;i++)//从1到r行
for(int j=1;j<=c;j++)//从1到c列
cin >> a[i][j]; for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
a[i][j] += max(a[i-1][j],a[i][j-1]);//从i-1和j-1可以看出，数组比矩阵多一行，多一列. //注意每一组的测试数据的结果之间有空行.
cout << "Scenario #" << k << ":" << endl << a[r][c] << endl << endl;
} return 0;
}
上述代码提交可以通过.
方法二：递归的方法
下面的代码测试数据通过，但是提交会超时(递归的原因?)
#include<iostream>
#include<algorithm>
using namespace std; int f(int **a,int r,int c,int x,int y)//递归函数
{
//x,y是起点下标
if(r-x==2 || c-y==2) //递归边界：起点在倒数第二行倒数第二列的位置
return a[x][y] + max(a[x+1][y],a[x][y+1]) + a[r-1][c-1];
else//递归：当前的位置的值 + max(以右边一个点为起点的结果,以下边的一个点为起点的结果)
return a[x][y] + max(f(a,r,c,x+1,y),f(a,r,c,x,y+1));
} int main()
{
int T,r,c;
cin >> T;
for(int k=1;k<=T;k++)
{
cin >> r >> c;
int ** a = new int*[r+1];
for(int i=0;i<r;i++)
{
a[i] = new int[c+1];
for(int j=0;j<c;j++)
cin >> a[i][j];
}
cout << "Scenario #" << k << ":" << endl << f(a,r,c,0,0) << endl << endl;
} return 0;
}