题目描述

几枚硬币被放置在n×m板的单元格中。位于棋盘左上角的机器人需要收集尽可能多的硬币，并将它们带到右下角的牢房。在每一步中，机器人可以将一个单元向右移动，或者从其当前位置向下移动一个单元。

输入

The fist line is n,m, which 1< = n,m <= 1000.
Then, have n row and m col, which has a coin in cell, the cell number is 1, otherwise is 0.

输出

The max number Coin-collecting by robot.

样例输入

5 6
0 0 0 0 1 0
0 1 0 1 0 0
0 0 0 1 0 1
0 0 1 0 0 1
1 0 0 0 1 0

样例输出

5

#include<stdio.h>
int a[1000][1000];
int dp[1000][1000];
int MAX(int a, int b)
{
	if (a > b)
		return a;
	else
		return b;
}
int find(int m, int n)
{
	dp[0][0] = a[0][0];
	int i, j;
	int max;
	for (i = 1; i < m; i++)
	{
		dp[i][0] = dp[i - 1][0] + a[i][0];
	}
	for (i = 1; i < n; i++)
	{
		dp[0][i] = dp[0][i - 1] + a[0][i];
	}
	for (i = 1; i < m; i++)
	{
		for (j = 1; j < n; j++)
		{
			max = MAX(dp[i - 1][j], dp[i][j - 1]);
			dp[i][j] = max + a[i][j];
		}
	}
	return dp[m - 1][n - 1];
}
int main()
{
	int m, n;
	scanf("%d%d", &m, &n);
	int i, j;
	for (i = 0; i < m; i++)
	{
		for (j = 0; j < n; j++)
		{
			scanf("%d", &a[i][j]);
		}
	}
	printf("%d\n", find(m, n));
	return 0;
}