当前位置: 首页 > news >正文

动态规划 —— 路径问题-下降路径最小和

1. 下降路径最小和

题目链接:

931. 下降路径最小和 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/minimum-falling-path-sum/description/

 

 


2.  算法原理 

状态表示:以莫一个位置位置为结尾

   

dp[i,j]表示:到达[i,j]位置的时候,此时的最小下降路径

2. 状态转移方程

  

根据最近的一步来划分问题:

      

                                以最小的下降路径到达A位置,然后再走一步到达目的地 

到达dp[i][j]有三种情况:

                               1. 从左上方位置过来:[i-1,j-1] -> [i,j],dp[i-1,j-1] + m[i][j]

                                                                                                 (缩写为x)     

     

                               2. 从正上方位置过来:[i-1,j] -> [i,j],dp[i-1,j] + m[i][j]

                                                                                                 (缩写为y)

     

                               3. 从右上方位置过来:[i-1,j+1] -> [i,j],dp[i-1,j+1] + m[i][j]

                                                                                                    (缩写为z)

     

本题的状态转移方程是:dp[i][j] = min(x,y,z)+m[i][j]

3. 初始化 :把dp表填满不越界,让后面的填表可以顺利进行

   

我们可以在上面的一行和左边还有右边的一列再额外的加上一行和两列的虚拟节点

    

原始矩阵里第一行的值是不能被改变的,不然会影响到最终结果,所以第一行的虚拟节点应该全部初始化为0,而左右两列不能初始化为0,因为为0的话就可能会参与最小值的计算,会影响到最终结果,所以应该初始化为正无穷大

    

本题的下标映射关系:因为本题给了一个矩阵,而我们又额外的加上一行和两列的虚拟节点,所以我们的下标都统一往右下角移动了一位,如果想找回之前对应的位置,那么下标需要进行统一减1(横纵坐标)

4. 填表顺序 

    

本题的填表顺序是:从上往下填写每一行,每一行的值是从左往右

5. 返回值 :题目要求 + 状态表示    

    

本题的返回值是:最后一行里面的最小值


3.代码 

动态规划的固定四步骤:1.  创建一个dp表

                                        2. 在填表之前初始化

                                        3. 填表(填表方法:状态转移方程)

                                        4. 确定返回值 

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {//本题是方形,所以不需要mint  n = matrix.size();//多加了一行两列,初始化先把虚拟节点都初始化为正无穷大vector<vector<int>>dp(n + 1, vector<int>(n + 2, INT_MAX));//将虚拟节点的第一行初始化为0for (int j = 0; j < n + 2; j++) dp[0][j] = 0;//额外的加上一行和两列的虚拟节点,所以从1开始for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)//这里的matrix[i-1][j-1]也是加上一行和一列的虚拟节点,所以要横纵-1dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1]))+ matrix[i - 1][j - 1];//返回最后一行里面的最小值//定义一个临时变量ret,不能将ret的的值定义为0,不然会影响到最终结果int ret = INT_MAX;for (int j = 1; j <= n; j++)ret = min(ret, dp[n][j]);//找到最后一行的最小和return ret;}
};


完结撒花~


http://www.mrgr.cn/news/62715.html

相关文章:

  • [ 问题解决篇 ] 新装虚拟机 Windows server 2012 无法 ping 通(关闭/开启防火墙详解)
  • 【python 将数据写入csv文件】正确方式
  • 聊一聊Qt中的按钮
  • 虚拟滚动 - 从基本实现到 Angular CDK
  • LinkedList和链表(下)
  • Android R S T U版本如何在下拉栏菜单增加基本截图功能
  • 什么是x86架构,什么是arm架构
  • 算法竞赛——02基本算法
  • AI机西好用吗?有哪些实用功能?真实用户体验告诉你!
  • 网鼎杯2024青龙组官方资格赛wp
  • 接入AI后,开源项目顿时有趣了
  • JVM(HotSpot):finally块的相关问题
  • CSS网页布局综合练习(涵盖大多CSS知识点)
  • 台州ctf市赛reverse(easy_choice)超详细复现
  • 什么是决策树桩
  • 因特网的概述和三种交换方式
  • C++笔记---可变参数模板
  • XHCI 1.2b 规范摘要(八)
  • 从零实现数据结构:二叉搜索树
  • 【HTML5标准】深度解析HTML5:前端开发的基石
  • 【深度学习】VITS语音合成原理解析
  • 向量库Milvus异常挂了,重新启动
  • 有没有优质的公司可以提供高质量大模型数据?
  • Vue.js(2) 基础:指令与功能概览
  • C++对象模型:Function 语意学
  • 九泰智库 | 医械周刊- Vol.65 | 广州发布首批创新药械产品目录