题目描述（中等难度）

依旧是的扩展，这个是输出从左上角到右下角，路径的数字加起来和最小是多少。

依旧在62题代码的基础上改，大家可以先看下 62 題。

解法一 递归

62 题中我们把递归 getAns 定义为，输出 （x，y）到 （m ，n ） 的路径数，如果记做 dp[x][y]。

那么递推式就是 dp[x][y] = dp[x][y+1] + dp[x+1][y]。

时间复杂度：

空间复杂度：

解法二

这里我们直接用 grid 覆盖存，不去 new 一个 n 的空间了。

  2.     int m = grid.length;
  3.     int n = grid[0].length;
  4.     //由于第一行和第一列不能用我们的递推式，所以单独更新
  5.     for (int i = 1; i < n; i++) {
  6.         grid[0][i] = grid[0][i - 1] + grid[0][i];
  8.     //更新第一列的权值
  9.     for (int i = 1; i < m; i++) {
  10.         grid[i][0] = grid[i - 1][0] + grid[i][0];
  11.     }
  12.     for (int i = 1; i < m; i++) {
  14.             grid[i][j] = Math.min(grid[i][j - 1], grid[i - 1][j]) + grid[i][j];
  16.         }
  17.     }
  18.     return grid[m - 1][n - 1];

时间复杂度：O（m * n）。

总

依旧是62题的扩展，理解了 62 题的话，很快就写出来了。

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^