有一个小游戏，在一个n*m的矩形网格里，每个网格里有一定数量的游戏币。我们可以控制机器人从左上角出发，到右下角结束。机器人只能往下或往右走，并且会失去沿途经过的格子里的游戏币。请计算机器人最多能得到多少游戏币。对下图所示的矩形网格，最多可以得到的游戏币数量为51。

解题思路：
(1)用map[i][j]记录(i，j)网格里游戏币的数量。那么从网格（1,1）到网格（i，j）得到最多的游戏币记录为dp[i][j]。
(2)第一个for循环将第0行和第0列都赋值为0，便于后续计数。
(3)第三个for循环中关键语句，如下↓

dp[i][j]=max(dp[i][j-1],dp[i-1][j])+map[i][j];

是通过递推得到的，显然，同一个子问题的解被多次用到了。

#include<iostream>

using namespace std;

#define N 100 

int max(int x,int y);

int main()
{//计算最多能得到多少游戏币. 
	int dp[N][N],map[N][N];
	for(int i=0;i<N;i++)
	{//将第0行，第0列赋值为0 
		dp[i][0]=dp[0][i]=0;
	}
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{//读入小地图信息 
			cin>>map[i][j];
		 } 
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dp[i][j]=max(dp[i][j-1],dp[i-1][j])+map[i][j];
		}
	 } 
	cout<<dp[m][n];
	return 0;
}

int max(int x,int y)
{
	return x>y ? x:y;
}