从左上到右下路径和的最值

给定一个矩阵m，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，返回所有路径中最小/大的路径和

分析
使用动态规划思路
dp[i][j]表示的是从原点到(i,j)位置的最短路径和，首先计算第一行和第一列，直接累加即可
对于其他位置，要么是从它左边的位置达到，要么是从上边的位置达到，我们取左边和上边的较小/大值，然后加上当前的路径值
if(i==0 && j==0) { matrix(0,0) }
if(i==0) { dp(i,j-1)+m(i,j) }
if(j==0) { dp(i-1,j)+m(i,j) }
else { min{dp(i,j-1) + m(i,j), dp(i-1,j) + m(i,j) }
or { max{dp(i,j-1) + m(i,j), dp(i-1,j) + m(i,j) }

public class DistanceInMatrix {

    /**
     *
     * @param matrix input matrix
     * @param flag if true, return min. if false, return max
     * @return distance
     */
    public int distance(int[][] matrix, boolean flag) {
        if (Optional.ofNullable(matrix).isEmpty() 
            || matrix.length <= 0 || matrix[0].length <= 0) {
            return 0;
        }

        int rows = matrix.length;
        int columns = matrix[0].length;
        int[][] dp = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = matrix[i][j];
                    continue;
                }

                if (i == 0) {
                    dp[i][j] = dp[i][j - 1] + matrix[i][j];
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + matrix[i][j];
                } else {
                    int m = dp[i][j - 1] + matrix[i][j];
                    int n = dp[i - 1][j] + matrix[i][j];
                    dp[i][j] = flag ? Math.min(m, n) : Math.max(m, n);
                }
            }
        }
        return dp[rows - 1][columns - 1];
    }

    public static void main(String[] args) {
        DistanceInMatrix distanceInMatrix = new DistanceInMatrix();
        int[][] matrix = new int[][]{
                {1, 3, 5, 9},
                {8, 1, 3, 4},
                {5, 0, 6, 1},
                {8, 8, 4, 0}
        };
        int result = distanceInMatrix.distance(matrix, true);
        System.out.println(result);
    }
}