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

资源限制

时间限制:1.0s 内存限制:256.0MB

问题描述

  有一个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.

sample input

three
1 3 3
2 2 2
3 1 2

sample output

eleven

Data scale and agreement

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]);
	}
}