一、题目

有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。

第一行输入一个正整数n。
以下n行描述该方格。金币数保证是不超过1000的正整数。

输出最多能拿金币数量。

二、解题思路

开始想着从左上走到右下，可以用深度搜索试试。但是搜索出来的结果需要都记录下来，还要再比较大小，可能用的时间会很长，后来转念一想，既然是求最大收益，不如用DP。

DP数组可以设置大一点，因为数据约定n<=1000,所以直接设置DP[1000+10][1000+10]。这样还需要转移方程，DP[i][j]是经过（i，j）时最大金币数。而我们行进是只可以向右和向下，所以本最大收益是有两种情况，一种是从上边下来得到的，另一种是从左边过来得到的，所以最终转移方程如下：

三、完整代码