Minimum Path Sum

- 日理万妓 2022-09-26 03:11 107阅读 0赞

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

稍加改进变成一个简单版的迷宫问题。

public static void main(String[] args) {	 
    		int[][] a = new int[][]{
    			{1,1,0,0,0},
    			{1,3,1,0,1},
    			{1,1,4,1,1},
    			{0,2,0,1,0},
    			{0,1,1,1,1}
    			};	
    		 search(a);
    	}
    	public static int search(int[][] a){
    		if(a.length==0){
    			return 0;
    		}
    		int r= a.length;
    		int c= a[0].length;
    		int[][] cost= new int[r][c];
    		cost[0][0]=a[0][0];
    		int flag=0;
    		for (int i = 1; i < c; i++) {
    			if(flag==1){
    				cost[0][i]=Integer.MAX_VALUE;//表示此路不通
    			}
    			if(a[0][i]==0&&flag==0){
    				cost[0][i]=Integer.MAX_VALUE;//表示此路不通
    				flag=1;
    			}
    			if(flag==0){
    				cost[0][i]=cost[0][i-1]+a[0][i];
    			}
    			
    			
    		}
    		flag=0;
    		for (int i = 1; i < r; i++) {
    			if(flag==1){
    				cost[i][0]=Integer.MAX_VALUE;
    			}
    			if(a[i][0]==0&&flag==0){
    				cost[i][0]=Integer.MAX_VALUE;
    				flag=1;
    			}
    			if(flag==0){
    				cost[i][0]=cost[0][i-1]+a[i][0];
    			}
    			
    		}
    		for (int i =1 ; i < r; i++) {
    			for (int j = 1; j < c; j++) {
    				if(a[i][j]==0){
    					cost[i][j]=Integer.MAX_VALUE;
    				}else{
    					if(cost[i-1][j]==Integer.MAX_VALUE&&cost[i][j-1]==Integer.MAX_VALUE){
    						cost[i][j]=Integer.MAX_VALUE;
    					}else{
    						cost[i][j] = Math.min(cost[i-1][j], cost[i][j-1])+a[i][j];
    					}
    				}
    				
    			}
    		}
    		System.out.println(cost[r-1][c-1]);
    		return cost[r-1][c-1];
    	}