当前位置: 首页 > 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.lryc.cn/news/473475.html

相关文章:

  • 【Linux网络】TCP_Socket
  • NVR批量管理软件/平台EasyNVR多个NVR同时管理支持视频投放在电视墙上
  • Springboot集成阿里云通义千问(灵积模型)
  • 微信公众号(或微信浏览器)获取openId(网页授权)
  • C++算法第五天
  • 牛客网剑指Offer-树篇-JZ26 树的子结构
  • FFmpeg 4.3 音视频-多路H265监控录放C++开发六,使用SDLVSQT显示yuv文件
  • Spring 设计模式之适配器模式
  • 多传感器数字化分析系统
  • Java 基础教学:面向对象编程基础-封装、继承与多态
  • Ubuntu环境本地部署DbGate数据库管理工具并实现无公网IP远程访问
  • 【AI抠图整合包及教程】Meta SAM 2:视觉分割的革命性飞跃
  • 使用语言模型进行文本摘要的五个级别(llm)
  • ubuntu交叉编译libffi库给arm平台使用
  • 【jvm】空间分配担保策略
  • iQOO手机怎样将屏幕投射到MacBook?可以同步音频吗?
  • BUU usualCrypt1
  • 第十七章 标准库特殊设施
  • 【格言分享】程序员的经典名言解读
  • SpringBoot接收LocalDateTime参数
  • Typora配置GitHub图床--结合PicGo
  • 【书生.浦语实战营】——入门岛
  • WPF+MVVM案例实战(十四)- 封装一个自定义消息弹窗控件(下)
  • 嵌入式——STM32外设应用
  • HCIA(ACL)
  • react基础之reactHooks
  • Java基础0-Java概览
  • SW绘制曲面
  • css知识点梳理2
  • 攻防世界 MISC miao~详解