题面
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 }