每天手撕一道算法-64. 最小路径和

/*
这题的意思是从左上角到右下角，（注意：每次是向下或者向右移动一格），所走过的路径数字和要求最小。

这道题要用动态规划，在原来的数组上去改变值。先从最近的开始，得到最优解，再慢慢递推到外面一层。
*/
class Solution {
    public int minPathSum(int[][] a) {

        for (int i = 0; i < a.length; i++)
            for(int j = 0; j < a[0].length; j++) {
                if (i == 0 && j == 0) continue; // 略过左上角的值
                // 最上面一行，值更新为左边的数+现在的数。因为只能从左边过来。
                else if (i == 0) a[i][j] += a[i][j-1];
                // 最左边一列，值更新为上面的数+现在的数。因为只能从上边过来。
                else if (j == 0) a[i][j] += a[i-1][j];
                // 其余情况，要么从上面过来，要么从左边过来，选值小的那个
                else a[i][j] += Math.min(a[i-1][j],a[i][j-1]);
            }
        return a[a.length-1][a[0].length-1]; // 返回最后一个数
    }
}