import java.util.*;


public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0 ;
        int r_l = matrix.length ;
        int c_l = matrix[0].length ;
        //f[i][j]表示到达(i,j)的最小路径和
        int f[][] = new int[r_l][c_l] ;
        for(int i = 0 ; i < r_l ; i ++) {
            for(int j = 0 ; j < c_l ; j ++) {
                if(i == 0 && j == 0) {//原点
                    f[i][j] = matrix[i][j] ;
                } else if(i == 0) {//这能从左边来
                    f[i][j] = matrix[i][j] + f[i][j-1] ;
                } else if(j == 0) {//只能从上边来
                    f[i][j] = matrix[i][j] + f[i-1][j] ;
                } else {//可以从上边或者右边来,取最优方案
                    f[i][j] = matrix[i][j] + Math.min(f[i-1][j] , f[i][j-1]) ;
                }
            }
        }
        return f[r_l-1][c_l-1] ;
    }
}