##编程日记 动态规划问题：拿金币

##编程日记 动态规划问题：拿金币
资源限制
时间限制：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.util.Scanner;

public class WinterVacation08 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int a=scanner.nextInt();
        int[][] ints=new int[a][a];
        int[][] ints1=new int[a][a];
        for (int i=0;i 
这个答案并不是特别正确，但是我感觉思路是正确的，100分的测试只有70分，另外是内存消耗大，具体答案还希望各位童鞋给出！！！
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5722404.html