网站建设公司网站源码,建工网首页,金山网站制作,河南省建筑资质查询1. 题目解析
题目链接#xff1a;931. 下降路径最小和 这个问题的理解其实相当简单#xff0c;只需看一下示例#xff0c;基本就能明白其含义了.
2.算法原理
对于这类路径类问题#xff0c;通常我们首先需要分析状态表示以及状态转移的过程。特别地#xff0c;本题涉及…1. 题目解析
题目链接931. 下降路径最小和 这个问题的理解其实相当简单只需看一下示例基本就能明白其含义了.
2.算法原理
对于这类路径类问题通常我们首先需要分析状态表示以及状态转移的过程。特别地本题涉及的是路径上的最小值累加因此状态转移方程的设计尤为重要。
状态表示 我们选择的状态表示方式为dp[i][j] 代表到达位置 [i, j] 时所有下降路径中的最小和。这种定义方式有助于我们后续的状态转移和结果求解。状态转移方程 对于位置 [i, j]根据题目要求我们可以从上方、左上方或右上方三个方向转移而来。我们需要找到这三个方向中的最小值并加上当前位置 [i, j] 的值从而得到到达该位置的最小路径和。因此状态转移方程为dp[i][j] min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j 1])) matrix[i][j]。初始化 为了简化计算我们可以在矩阵的上方额外添加一行辅助结点并将其值初始化为0。这样做的好处在于当我们计算第一行时可以直接引用这些辅助结点的值而无需进行额外的判断。同时考虑到状态转移时可能需要访问到 [i, j - 1] 和 [i, j 1] 这样的位置我们可能需要在矩阵的两侧也额外添加列并初始化这些列的值。通常情况下这些辅助结点的值需要保证后续填表过程的正确性。在本题中由于我们关心的是路径上的最小值累加因此将辅助结点的值初始化为0是合理的。填表顺序 根据状态表示和状态转移方程我们可以确定填表的顺序是从上往下逐行计算。这样做的原因是在计算当前行的某个位置时我们只需要依赖上一行的数据这符合动态规划的自底向上思想。返回值 题目要求的是只要到达最后一行即可因此我们的目标是找到最后一行中的最小值。这可以通过遍历最后一行并比较各个位置的值来实现。最终返回的是这个最小值而不是 dp[m][n] 的值因为 dp[m][n] 只表示到达特定位置 [m, n] 的最小路径和而题目要求的是到达最后一行任意位置的最小路径和。
3.代码编写
class Solution
{
public:int minFallingPathSum(vectorvectorint matrix) {int n matrix.size();vectorvectorint dp(n 1, vectorint(n 2, INT_MAX));for(int j 0; j n 2; j) dp[0][j] 0;for(int i 1; i n; i){for(int j 1; j n; j){dp[i][j] min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j 1])) matrix[i - 1][j - 1];}}int ret INT_MAX;for(int i 1; i n; i) ret min(ret, dp[n][i]);return ret;}
};
The Last
嗯就是这样啦文章到这里就结束啦真心感谢你花时间来读。
觉得有点收获的话不妨给我点个赞吧
如果发现文章有啥漏洞或错误的地方欢迎私信我或者在评论里提醒一声~
