自建电商平台方案,seo优化排名易下拉效率,wordpress 主题怎么用,国内小程序开发公司动态规划-----路径问题 下降最小路径和1#xff1a;状态表示2#xff1a;状态转移方程3 初始化4 填表顺序5 返回值6 代码实现 总结#xff1a; 下降最小路径和 1#xff1a;状态表示
假设#xff1a;用dp[i][j]表示#xff1a;到达[i,j]的最小路径
2#xff1a;状态转… 动态规划-----路径问题 下降最小路径和1状态表示2状态转移方程3 初始化4 填表顺序5 返回值6 代码实现 总结 下降最小路径和 1状态表示
假设用dp[i][j]表示到达[i,j]的最小路径
2状态转移方程
结合图片分析 如果图中的A点要到达三角形那么就会考虑下A点上面的数通过最小路径到达A。 那么通过路径变为 x-A-三角形 那么我们如何找到到达A点的下降路径呢 由状态表示用dp[i][j]表示到达[i,j]的最小路径。 则我们可以转换我到达A点的最小路径为dp[i-1][j-1]或dp[i-1][j]或dp[i-1][j1] 文字总结在dp表中每一个位置向下都有3种情况根据这三种情况可以规划处动态方程
因为要最小路径和那么我们就可以在三个路径下取最小的路径这就要用到min
dp[i][j] min(dp[i-1][j-1],min(dp[i][j-1],dp[i][j1]))d[i][j]----------状态转移方程3 初始化 初始化的目的是防止越界访问的问题 由状态转移方程得出dp[i][j] min(dp[i-1][j-1],min(dp[i][j-1],dp[i][j1]))d[i][j]由状态转移方程可以得出我们需要上方的3个元素分别是: [i,j-1]、[i,j]、[i,j1]
所以我们需要添加1行2列去避免数组越界的问题圈圆圈的就是会越界的地方 【注意事项】 1虚线里面的值是要保证不影响后面的操作第一行就不要影响圆圈的值就可以把第一行初始化成0 对于列不要影响最小值的比对:min(x,y,z)那么把列初始化为正无穷大
2d表对应dp表下标的映射
4 填表顺序
填表顺序从下往上因为是对于填表左右对状态方程没有什么影响,而上下是有影响的
5 返回值
返回最后一列的最小值
6 代码实现
class Solution {
public:int minFallingPathSum(vectorvectorint matrix) {//创建dp表int mmatrix.size();int nmatrix[0].size();vectorvectorint dp(m1,vectorint((n2),INT_MAX));for(int i0;in2;i)//初始化dp[0][i]0;//填表for(int i1;im;i)for(int j1;jn;j)dp[i][j]min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j1]))matrix[i-1][j-1];//返回结果int retINT_MAX;for(int i1;in;i)retmin(ret,dp[n][i]);return ret;}
};总结
对于路径问题 第一分析状态 第二列出状态方程 第三初始化(防止越界访问) 第四填表顺序(由状态方程的出填表顺序) 第五得出返回值
