题解 | #矩阵的最小路径和#
矩阵的最小路径和
https://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb
2022.0816算法第31题矩阵的最小路径和
一样的套路，动态规划问题，相当于对路的方案数进行加权。
1、状态矩阵dp
为到达i，j位置的最小路径和
vector<vector<int>> dp=matrix;2、初始值
将边界的值进行修改，进行向上累加。
int n=matrix.size();
int m=matrix[0].size();
for(int i=1;i<n;i++){
dp[i][0]=dp[i][0]+dp[i-1][0];
}
for(int i=1;i<m;i++){
dp[0][i]=dp[0][i]+dp[0][i-1];
}
3、状态转移方程
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i][j];和路径数差不多
4、返回目标点的值
return dp[n-1][m-1];也可以采用递归的方法。
叠纸游戏公司氛围 15人发布
投递美团等公司10个岗位