/**

 * 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 class Q64MinimumPathSum {

    public static void main(String[] args) {

    }

    public int minPathSum(int[][] grid) {

        int m = grid.length;

        int n = grid[0].length;

        //求出最左边一行的每个点对应的最小和

        for (int i = 1; i < m; i++) {

            grid[i][0] += grid[i-1][0];

        }

        //最上边行的

        for (int i = 1; i < n; i++) {

            grid[0][i] += grid[0][i-1];

        }

        //前两个是判断特殊情况

        if (m == 1)

            return grid[0][n-1];

        else if (n == 1)

            return grid[m-1][0];

        //动态规划主体

        else

        {

            int temp;

            for (int i = 1; i < m; i++) {

                for (int j = 1; j < n; j++) {

                    //求该点的最小和

                    temp = Math.min(grid[i-1][j],grid[i][j-1]);

                    grid[i][j] += temp;

                }

            }

            //右下角的点

            return grid[m-1][n-1];

        }

    }

}