百度推广区域代理黑帽seo工具

题目描述：（来自LeetCode）

思路：用dp[i][j]表示从[0][0]走到[i][j]这一格的最短路径和，在起点dp[i][j]=grid[0][0]的，当在第一行和最后一列的时候，比较特殊，到达第一行某一个一定是从左侧过来的，到达第一列某一格，一定是从上面过来的，因为只能向下和向右走，因此，我们可以得到动态转移方程

当i>0且j=0时，dp[i][0]=dp[i-1][0]+grid[i][0]

当j>0且i=0时，dp[i][0]=dp[0][j-1]+grid[0][j]

当i>0且j>0时，dp[i][j]=min(dp[i-1][j],dp[i[j-1])+grid[i][j]

代码实现：

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m=grid.size();int n=grid[0].size();int dp[m][n];memset(dp,0,sizeof(dp));//初始化dp[0][0]=grid[0][0];for(int i=1;i<m;i++)  dp[i][0] = grid[i][0] + dp[i-1][0];for(int i=1;i<n;i++) dp[0][i]=grid[0][i]+dp[0][i-1];for(int i=1;i<m;i++){for(int j=1;j<n;j++){dp[i][j]+=min(dp[i-1][j],dp[i][j-1])+grid[i][j];}} return dp[m-1][n-1];}
};

状态压缩：其实当走到第i行的时候，最短路径和只与第i-1行和第i行有关，而且，每一格都是在左边和上边一个中取最小值再加上当前的元素，我们只用一个一维数组来表示即可dp[i]就表示从[0][0]到第i-1行的最短路径和，这样，其实当我们计算走到第i行的最短路径时，dp[i]目前存的其实还是上一行的最短路径，也就是该二维的时候，这一个上面的路径和，而i-1存的就是二维数组里这一格左边的元素，所以dp[i][j]=min(dp[i-1][j],dp[i[j-1])+grid[i][j]就可以转化成dp[j]=min(dp[j],dp[j-1])+grid[i][j]

代码实现c++：

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m=grid.size();int n=grid[0].size();int dp[n];memset(dp,0,sizeof(dp));//初始化dp[0]=grid[0][0];for (int i = 0; i < m ; i++) {for (int j = 0; j < n ; j++) {if (i == 0 && j != 0) {dp[j] = grid[i][j] + dp[j - 1];} else if (i != 0 && j == 0) {dp[j] = grid[i][j] + dp[j];} else if (i != 0 && j != 0) {dp[j] = grid[i][j] +min(dp[j], dp[j - 1]);}}}return dp[n-1];}
};

空间优化:

从起点到终点往后找最短路的时候，每次只需要更新过的就可以了，故可以直接用原数组空间

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int n=grid[0].size();int m=grid.size();if(m==0||n==0) return 0;for(int i=1;i<m;i++) grid[i][0]+=grid[i-1][0];for(int j=1;j<n;j++) grid[0][j]+=grid[0][j-1];for(int i=1;i<m;i++){for(int j=1;j<n;j++){grid[i][j]+=min(grid[i-1][j],grid[i][j-1]);}}return grid[m-1][n-1];}
};

动态规划还在学习中，下周会更新一个动态规划讲解，也是督促自己学习，明天见~