题面

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.

给定二维数组,从(0, 0)开始,只能向右和向下走,找到最小的路径和。

样例

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

思路

动态规划,打表。我们就模拟移动的路径。我们需要一个二维数组来存储每一步的路径值。

可以在原来二维数组基础上,直接进行操作。

第一排只能向右走得到;第一列只能向下走得到。

其他的就要参考它的上边元素值和左边元素值,取小在加上它本身,更新成为它。(因为要最小路径,所以我们要确保每一步都最小)

算法

1. 遍历第一行,当前元素值为它左边元素加上它本身(只能从左边向右边走);

2. 遍历第一列,当前元素值为它上边元素加上它本身(只能从上边向下边走);

3. 遍历二维数组其他元素,当前值为上边元素与左边元素最小值加上它本身;

4. 返回右下角元素,即是结果。

时间复杂度:O(n2)

空间复杂度:O(n2)

源码

 1 class Solution {
 2 public:
 3     int minPathSum(vector<vector<int>>& grid) {
 4         int row = grid.size(), col = grid[0].size();
 5         if(row == 0)
 6             return 0;
 7         for(int i=1; i<col; i++)
 8         {
 9             grid[0][i] += grid[0][i-1];
10         }
11         for(int i=1; i<row; i++)
12         {
13             grid[i][0] += grid[i-1][0];
14         }
15         for(int i=1; i<row; i++)
16         {
17             for(int j=1; j<col; j++)
18             {
19                 grid[i][j] += min(grid[i][j-1], grid[i-1][j]);
20             }
21         }
22         return grid[row-1][col-1];
23     }
24 };

优化:空间压缩

其实,我们在做的过程当中,一直在做行处理,即一直在更新某一行(更新完这一行就转向下一行)。那么,我们只需要一个一维数组即可解决这个问题。

这样一来,空间就压缩到了O(n),时间复杂度不变。

(1-压缩后的;2-压缩前的)似乎空间占用也没有多大变化,但是我们确实做了空间压缩。

空间压缩源码

只用一维数组在存储状态,就要重新推导一下更新的状态方程

第一行:dp[0] = grid[0][0]

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

其他行:dp[0] = grid[i][0] + dp[0]

    dp[j] = grid[i][j] +  min(dp[j-1], dp[j])

 1 int minPathSum(vector<vector<int>>& grid) {
 2         int row = grid.size(), col = grid[0].size();
 3         if(row == 0)
 4             return 0;
 5         vector<int> dp(col, 0);//只要额外一维数组的空间,上一种做法,如果不原地使用原来二位数组的话,就只能额外开二维数组。
 6         dp[0] = grid[0][0];
 7         for(int i=1; i<col; i++)
 8         {
 9             dp[i] = dp[i-1] + grid[0][i];
10         }
11         for(int i=1; i<row; i++)
12         {
13             dp[0] += grid[i][0];
14             for(int j=1; j<col; j++)
15             {
16                 dp[j] = min(dp[j-1], dp[j]) + grid[i][j];
17             }
18         }
19         return dp[col-1];
20     }