# 算法训练 拿金币(Algorithm training takes gold coins)-其他

## 算法训练 拿金币(Algorithm training takes gold coins)

### 问题描述

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

### 输入格式

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

最多能拿金币数量。

3
1 3 3
2 2 2
3 1 2

11

n<=1000

### 提交代码

``````import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(new BufferedInputStream(System.in));
int num = scanner.nextInt();
//dp数组含义：走到第i行，第j列位置时，金币的最大值
int dp[][] = new int[num][num];
for(int i = 0;i<num;i++){
for(int j = 0;j<num;j++){
dp[i][j] = scanner.nextInt();
}
}
//dp数组第一行赋值
for(int i = 1;i<num;i++){
dp[0][i] = dp[0][i-1]+dp[0][i];
}
//dp数组第一列赋值
for(int i = 1;i<num;i++){
dp[i][0] = dp[i-1][0]+dp[i][0];
}
//因为只能向右或者向下走，所以走到第i行第j列的最大值，即为走到第i-1行第j列的值与走到第i行第j-1列的最大值与第i行第j列的值之和
for(int i = 1;i<num;i++){
for(int j = 1;j<num;j++){
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])+dp[i][j];
}
}
//dp数组右下角的值即为最大值
System.out.println(dp[num-1][num-1]);
}
}

``````
————————

### Resource constraints

Time limit: 1.0s memory limit: 256.0mb

### Problem description

There is an n x n grid. Each grid has some gold coins. You can get the gold coins as long as you stand in the grid. You stand in the top left corner of the grid, and you can walk from one grid to the right or lower grid at a time. How can I get the most gold coins.

### Input format

On the first line, enter a positive integer n.
The following N lines describe the grid. The number of gold coins is guaranteed to be a positive integer not exceeding 1000.

### Output format

The maximum number of gold coins you can take.

three
1 3 3
2 2 2
3 1 2

eleven

n<= one thousand

### Submit code

``````import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(new BufferedInputStream(System.in));
int num = scanner.nextInt();
//dp数组含义：走到第i行，第j列位置时，金币的最大值
int dp[][] = new int[num][num];
for(int i = 0;i<num;i++){
for(int j = 0;j<num;j++){
dp[i][j] = scanner.nextInt();
}
}
//dp数组第一行赋值
for(int i = 1;i<num;i++){
dp[0][i] = dp[0][i-1]+dp[0][i];
}
//dp数组第一列赋值
for(int i = 1;i<num;i++){
dp[i][0] = dp[i-1][0]+dp[i][0];
}
//因为只能向右或者向下走，所以走到第i行第j列的最大值，即为走到第i-1行第j列的值与走到第i行第j-1列的最大值与第i行第j列的值之和
for(int i = 1;i<num;i++){
for(int j = 1;j<num;j++){
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])+dp[i][j];
}
}
//dp数组右下角的值即为最大值
System.out.println(dp[num-1][num-1]);
}
}

``````