腾讯笔试实习，第三题玩游戏攻击力问题

import java.util.Scanner;
/**
 * @author Administrator
 *	二维数组中	
 *	从左下到右下最短的路劲之和与具体路径;
 */

public class tMain {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int m=in.nextInt();
		
		int arr[][]=new int[n][m];
		
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				arr[i][j]=in.nextInt();
			}
		}
		char ch[][]=fun(arr);
		System.out.println(search(ch, arr));
		
	}
    // 保存路径数组
	public static char[][] fun(int arr[][]) {
		int hang=arr.length;
		int lie=arr[0].length;
		int dp[][]=new int[hang][lie];
		dp[0][0]=arr[0][0];
		int res=arr[0][0];
		
		char ch[][]=new char[hang][lie];
		ch[0][0]='o';
		
		for(int i=1;i<hang;i++){
			dp[i][0]=dp[i-1][0]+arr[i][0];
			ch[i][0]='d';
			
		}
		for(int j=1;j<lie;j++){
			dp[0][j]=dp[0][j-1]+arr[0][j];
			ch[0][j]='r';
		}
		
		for(int i=1;i<hang;i++){
			for(int j=1;j<lie;j++){
				if(dp[i-1][j]<dp[i][j-1]){
					ch[i][j]='d';
				}else{
					ch[i][j]='r';
				}
				dp[i][j]=Math.min(dp[i-1][j], dp[i][j-1])+arr[i][j];
			}
		}
		for(int i=0;i<hang;i++){
			for(int j=0;j<lie;j++){
				System.out.print(ch[i][j]+" ");
			}
			System.out.println();
		}
		return ch;
		
	}
    //根据路径查找路劲最大的值
	public static int search(char ch[][],int arr[][]) {
		int hang=arr.length;
		int lie=arr[0].length;
		int i=hang-1,j=lie-1;		
		int res=arr[i][j];
		int temp=res;
			while(true){
				if(ch[i][j]=='r'){
					System.out.print(ch[i][j]);
					res=Math.max(arr[i][j-1], temp);
					j--;
				}else if((ch[i][j]=='d')){
					System.out.print(ch[i][j]);
					res=Math.max(arr[i-1][j], temp);
					i--;
				}else{
					System.out.print(ch[i][j]);
					break;
				}
				temp=res;
			}
			System.out.println();
			return res+1;
	}

}