Minimum Path Sum-蒲公英云

Minimum Path Sum

- 日理万妓 2022-09-26 03:11 221阅读 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];
    }