package leecode;


/**
 *
 * 64. 最小路径和
 *
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 *
 * 说明：每次只能向下或者向右移动一步。
 *
 *
 * @author Tang
 * @date 2021/9/7
 */
public class MinPathSum {


    /**
     * 动态规划解决二维数组问题
     * 老规矩
     * x :每一个元素
     * f(x) :从起始位置到该元素的最小路径值
     * f(x) = MAX( f(y), f(z) )+1  y为x左边元素，z为x上边元素
     *
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        if(grid.length == 0) {
            return 0;
        }
        int down = grid.length;
        int right = grid[down-1].length;

        //构建备忘录
        int[][] tables = new int[down][right];

        /**
         *  优先按列处理
         */
        for(int i = 0; i < down; i++) {
            for(int j = 0; j < right; j++) {
                if(i == 0 && j == 0){
                    tables[i][j] = grid[i][j];
                    continue;
                }

                if(i == 0) {
                    tables[i][j] = tables[i][j-1] + grid[i][j];
                    continue;
                }
                if(j == 0) {
                    tables[i][j] = tables[i-1][j] + grid[i][j];
                    continue;
                }
                tables[i][j] = Math.min(tables[i-1][j], tables[i][j-1]) + grid[i][j];
            }
        }


        return tables[down-1][right-1];
    }

    public static void main(String[] args) {
        int[][] nums= {{1,2,3},{4,5,6}};
        System.out.println(new MinPathSum().minPathSum(nums));

    }

}