问题描述

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

输入格式

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

输出格式

　　最多能拿金币数量。

样例输入

3
1 3 3
2 2 2
3 1 2

样例输出

11

数据规模和约定

　　n<=1000

资源限制

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

解题思路：

        该题目属于DP类，即利用动态规划算法思想便可以求得最终解。在该问题中需要求的是最多能拿的金币数量，若采用递归算法思想，此时若数据集比较大，则会使得程序运行起来时间过长，故采用动态规划思想，将递归问题转化为非递归。首先输入矩阵大小 N * N ，然后创建一个相应的矩阵，并由程序自动输入赋初值，接着模拟从左上角走到右下角的过程。循环对数组每一行每一列的元素进行扫描，若当前位置为最左上角，则此时最大金币数量为该位置的金币数量；若当前位置为第一行位置(i == 0 && j > 0)，则此时最大金币数量为该位置的金币数量加上该位置的左边位置的金币数量；若当前位置为第一列位置(j == 0 && i > 0)，则此时最大金币数量为该位置的金币数量加上该位置的上边位置的金币数量；除了上述三种情况外就是在矩阵内部而不是边缘的情况下，该位置的最大金币数量与该位置的上面和左边两个位置有关(模拟从左上角走到右下角的过程中，途径该位置肯定是从该位置的左边往右走或者是来自于该位置的上面往下走才到该位置上的)，故先判断该位置的上面和左边两个位置的金币数量，选择较大的一个加上该位置原有金币数量，即得到该位置最大金币数量。该算法的Java实现如下：

import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int[][] arr = new int[num][num];
        for (int i = 0; i < num; i++) {
			for (int j = 0; j < num; j++) {
				arr[i][j] = scanner.nextInt();
            }
        }
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                if (i == 0 && j == 0){
                }else if (i == 0 && j > 0){
					arr[i][j] += arr[i][j - 1];
                }else if (j == 0 && i > 0){
                    arr[i][j] += arr[i - 1][j];
                }else {
                    if (arr[i - 1][j] > arr[i][j - 1]){
						arr[i][j] += arr[i - 1][j];
                    }else {
                        arr[i][j] += arr[i][j - 1];
                }
            }
        }
    }
    System.out.println(arr[num - 1][num - 1]);
    scanner.close();
	}
}

        在该算法中，算法的时间复杂度为O()，空间复杂度为O(1)。