哪个网站适合 做红本抵押设计网站一般多少钱

64. 最小路径和 - 力扣（LeetCode）

和这一题特别像：LeetCode第 120 题：三角形最小路径和(C++)_qq_32523711的博客-CSDN博客）

动态规划典型题目，状态方程如下

非边界，当i、j 均不为0时：

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

$$f[0][0]=grid[0][0]$$

边界时（左边界j=0，上边界i=0）

$$f[i][0]=f[i-1][0]+grid[i][0]$$

$$f[0][i]=f[0][i-1]+grid[0][i]$$

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int row = grid.size();int col = grid[0].size();vector<vector<int>> f(row, vector<int>(col, 0));f[0][0] = grid[0][0];for (int i = 1; i < row; ++i) //左边界f[i][0] = f[i - 1][0] + grid[i][0];for (int i = 1; i < col; ++i) //上边界f[0][i] = f[0][i - 1] + grid[0][i];for (int i = 1; i < row; ++i){ //其他for (int j = 1; j < col; ++j)f[i][j] = min(f[i][j - 1], f[i - 1][j]) + grid[i][j];}return f[row - 1][col - 1];}
};

换个写法，思路更加清晰：

第一次循环，根据第一行的左边界f[0][0]（已知）计算出第一行的剩余元素；

剩下的每一次循环之前，先计算当前行的左边界元素，然后根据左边界元素和上一行元素，计算出当前行的剩余元素。

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int row = grid.size();int col = grid[0].size();vector<vector<int>> f(row, vector<int>(col, 0));f[0][0] = grid[0][0];for (int i = 0; i < row; ++i){//先考虑行if(i != 0) f[i][0] = f[i-1][0] + grid[i][0];  //计算当前行的左边界元素for (int j = 1; j < col; ++j){if(i == 0) //如果是上边界（第一行）f[0][j] = f[0][j - 1] + grid[i][j];elsef[i][j] = min(f[i][j - 1], f[i - 1][j]) + grid[i][j];}}return f[row - 1][col - 1];}
};

可以看到空间复杂度为O(m*n)，为辅助数组的占用空间。

下面进行一下优化吧，由状态方程可以看到，每一行的元素值只与该行元素和上一行元素有关，所以其实不需要n x m的额外空间（和这个类似：LeetCode第 120 题：三角形最小路径和(C++)_qq_32523711的博客-CSDN博客）。

一般这种情况我们可以使用滚动数组减少空间消耗，两行（2xn）交替使用就可以，更甚，其实一行(1xn)就可以。

直接考虑一行(1xn)，代码：

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int row = grid.size();int col = grid[0].size();vector<int> f(col, 0);for (int i = 0; i < row; ++i){f[0] = f[0] + grid[i][0]; //左边界f[0](第一列)for (int j = 1; j < col; ++j){if(i == 0) //如果是上边界（第一行）f[j] = f[j-1] + grid[i][j];elsef[j] = min(f[j - 1], f[j]) + grid[i][j];} }return f[col - 1];}
};

滚动数组(2xn)的也写一下：

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int row = grid.size();int col = grid[0].size();vector<vector<int>> f(2, vector<int>(col, 0));f[0][0] = grid[0][0];int cur; //滚动数组下标int pre; //滚动数组下标for (int i = 0; i < row; ++i){//先考虑行cur = i % 2; //要么1要么0）pre = 1-cur; //要么0要么1if(i != 0) f[cur][0] = f[pre][0] + grid[i][0];  //计算当前行的左边界元素for (int j = 1; j < col; ++j){if(i == 0) //如果是上边界（第一行）f[cur][j] = f[cur][j - 1] + grid[i][j];elsef[cur][j] = min(f[cur][j - 1], f[pre][j]) + grid[i][j];}}return f[cur][col - 1];}
};

更奇葩的也还有，空间复杂度O(1)，直接在原数组上修改就行（因为每个数只会用到一次），思路和第一段代码一样，只是存储的时候稍作修改即可。。。不过，个人不是很推荐，修改原数组毕竟不太好。。吧。。。

这个题使用回溯的思路也是可以的，而且剪枝也简单（路径和大于当前最小路径和就直接cut掉）