棋盘左上角到右下角路径最大值问题

企鹅 2016 实习生招聘 程序题1：

给出一M*N的矩阵，每个格子中都有一个非负整数，只能向右或向下移动，求从左上角到右下角的所有路径中的最大值（每条路径的值为对路径中所进过的格子中的数求和）。

输入格式：

4 5

1 0 0 8 0

0 0 3 0 0

4 0 0 5 0

0 6 0 0 0

参考上述链接，使用动态规划方法，求出最大值。

虽然题目只要求求出最大值，我觉得还是求一下路径比较稳妥，万一以后遇到也有个思路；方法：使用逆推的方法，从后向前，一步步求出所经过的路径。

package ptc;

import java.util.*;


public class test {

	public static void main(String[] args) {  
        
		Scanner sc = new Scanner(System.in);
		
		while(sc.hasNextLine()){
			//读入m,n
			int m = sc.nextInt();
			int n = sc.nextInt();
			//读入矩阵
			int [][] mat = new int [m][n];
			for(int i=0; i<m; i++){
				for(int j=0; j<n; j++){
					mat[i][j] = sc.nextInt(); 
				}
			}
			
			System.out.println("最大值为： " + getMaxPath(m,n,mat));
			
		}
        
        
    }  
	
	public static int getMaxPath( int m, int n , int[][] matr ){
		
		int path[][] = new int [m+n-1][2];
		path[0][0] = 0;
		path[0][1] = 0;
		path[m+n-2][0] = m-1;
		path[m+n-2][1] = n-1;
		
		for(int i=1; i<n; i++){
			matr[0][i] += matr[0][i-1];
		}
		for(int j=1; j<m; j++){
			matr[j][0] += matr[j-1][0];
		}
		
		for(int i=1; i<m; i++){
			for(int j=1; j<n; j++){
				matr[i][j] += max(matr[i-1][j] , matr[i][j-1]);
			}
		}
		
		
		/** 使用反推法，从最后一个点向前推倒，找出路径 */
		for(int i=m-1; i>=0; i--){
			for(int j=n-1; j>=0; j--){
				
				if(i==0 &&j==0){
					//反推回到了起点
					break;
				}
				
				if(i==0){
					//如果反推到了第一行，只能向左继续推
					path[i+j-1][0] = 0;
					path[i+j-1][1] = j-1;
				}else if(j==0){
					//如果反推到了第一列，只能向上继续推
					path[i+j-1][0] = i-1;
					path[i+j-1][1] = 0;
				}else if(matr[i-1][j] > matr[i][j-1]){			
					path[i+j-1][0] = i-1;
					path[i+j-1][1] = j;
				}else{
					path[i+j-1][0] = i;
					path[i+j-1][1] = j-1;
				}
			}
		}
		
		/** 打印路径 */
		for(int i=0; i<m+n-1; i++){
			System.out.println(" ( " + (path[i][0]) + " , " + (path[i][1]) + " )");
		}
		
		
		return matr[m-1][n-1];
		
	}
	public static int max(int a, int b){
		if(a>b){
			return a;
		}else{
			return b;
		}
	}
	
}  
	
/*结果：
	4 5
	1 0 0 8 0
	0 0 3 0 0
	4 0 0 5 0
	0 6 0 0 0
	 ( 0 , 0 )
	 ( 0 , 1 )
	 ( 0 , 2 )
	 ( 0 , 3 )
	 ( 1 , 3 )
	 ( 2 , 3 )
	 ( 3 , 3 )
	 ( 3 , 4 )
	最大值为： 14*/