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

### 回答1：
可以使用动态规划来解决这个问题。设f[i][j]表示从左上角走到第i行第j列格子时所能拿到的最多金币数。则有状态转移方程：

f[i][j] = max(f[i-1][j], f[i][j-1]) + a[i][j]

其中a[i][j]表示第i行第j列格子里的金币数。最终答案为f[n][n]。

具体实现时，可以使用一个二维数组来存储f[i][j]的值，从左上角开始逐行逐列计算，最终得到f[n][n]的值即为最多能拿到的金币数。

### 回答2：
这个问题可以采用动态规划的思想来解决。首先，我们可以定义一个二维数组dp[i][j]，其中dp[i][j]表示走到第i行第j列时，最多能拿到的金币数量。由于我们要从左上角开始走，所以dp[1][1]就是我们想要求的答案。

接下来考虑如何求状态转移方程。我们可以发现，走到第i行第j列的金币数量与从哪个格子走过来有关。由于每次只能往右或往下走，所以我们只需要考虑从第i-1行第j列或者第i行第j-1列走过来的情况。具体来说，状态转移方程为：

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

其中a[i][j]表示第i行第j列的金币数量。意思就是在第i-1行第j列或者第i行第j-1列走过来的情况下，再加上当前格子里的金币数量，就是走到第i行第j列时最多能拿到的金币数量。

最后，我们只需要从dp[1][1]开始，按照状态转移方程依次计算dp数组中的每一个元素，最后dp[n][n]就是走到右下角最多能拿到的金币数量。同时，我们还可以记录路径，具体方法可以参考“背包问题”的解法。

总之，这个问题可以采用动态规划的思想来解决，时间复杂度为O(n^2)，可以有效地提高算法的效率。

### 回答3：
这是一个典型的动态规划问题。我们可以设计一个二维数组dp[i][j]，表示从起点走到(i,j)位置能够获得的最多金币数。初始状态为dp[0][0] = 该位置的金币数，因为起点自身已经包含一定的金币。

状态转移方程为：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + 该位置的金币数。即要么是从上面的格子走下来，要么是从左边的格子走过来，选择获得最多金币数的路径。

最后，dp[n-1][n-1]所表示的值就是从起点走到右下角能够获得的最多金币数。需要注意的是，在计算dp[i][j]时，要保证i-1和j-1都不越界。

实现上，可以遍历每一个位置(i,j)，按照上述状态转移方程计算dp[i][j]，最后返回dp[n-1][n-1]即可。时间复杂度为O(n^2)。