题目描述:(来自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];
}
};
动态规划还在学习中,下周会更新一个动态规划讲解,也是督促自己学习,明天见~