给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]] 输出：12
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200
这个题我用了两个解法，提交的解复杂度更优，使用了数组压缩技巧，如果实在看不懂另外一个解也是保过的，数组压缩这玩意没人强求，量力而行其他的就不多说了，上代码，看不懂的请留言或者私信，收到第一时间解答
class Solution {
/**典型的动态规划的问题，题意分析如下：（1）我们要从左上角走到右下角
（2）只能往右或者往下走，这意味这某个格子的上一步只能是它左边和它上面的格子
（3）计算的路径里包含左上和右下两个格子，别忘了加上*/
public int minPathSum2(int[][] grid) {
/**如果就一个格子，那你就站在终点上，没得选，直接把值返回 */
if(grid.length == 1 && grid[0].length == 1) {
return grid[0][0];
}
/**否则定义动态规划数组，dp[i][j]代表从左上角到(i,j)位置的最小路径和 */
int[][] dp = new int[grid.length][grid[0].length];
/**左上角没得选择 */
dp[0][0] = grid[0][0];
/**初始化第一行和第一列,第一行除了(0,0)都只能由它右边来*/
for(int j = 1; j < grid[0].length; j++) {
dp[0][j] = dp[0][j-1] + grid[0][j];
}
/**第一列只能从它上面位置来 */
for(int i = 1; i < grid.length; i++) {
dp[i][0] = dp[i-1][0] + grid[i][0];
}
/**初始化一般的位置*/
for(int i = 1; i < grid.length; i++) {
for(int j = 1; j < grid[i].length; j++) {
/**来到当前位置，上一步肯定是左边或者上面，谁小选谁 */
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[grid.length -1][grid[0].length - 1];
}
/**进阶版的动态规划，数组压缩技巧，思路就是我们当前的每一行肯定只依赖上一行，所以没有必要用一个二维数组
这是对空间的一个很大的浪费*/
public int minPathSum(int[][] grid) {
/**如果就一个格子，那你就站在终点上，没得选，直接把值返回 */
if(grid.length == 1 && grid[0].length == 1) {
return grid[0][0];
}
/**定义动态规划数组，计算到某一行i的时候dp[j]代表从左上角到(i,j)位置的最小路径和*/
int[] dp = new int[grid[0].length];
/**当前我们计算第一行，0位置是左上角，它没得选*/
dp[0] = grid[0][0];
/**初始化第一行*/
for(int j = 1; j < grid[0].length; j++) {
dp[j] = dp[j-1] + grid[0][j];
}
/**初始化一般的位置*/
for(int i = 1; i < grid.length; i++) {
for(int j = 0; j < grid[i].length; j++) {
/**来到当前位置，上一步肯定是左边或者上面，谁小选谁，左边就是dp[j-1]，上面就是dp[j](上一行计算的，这一样目前没有更新，一会更新)*/
dp[j] = j == 0? dp[j] + grid[i][j] : Math.min(dp[j-1],dp[j]) + grid[i][j];
}
}
return dp[grid[0].length - 1];
}
}