动规训练2

一、最小路径和

1、题目解析

就是一个人从左上往做下走,每次只能往右或者往下,求他到终点时,路径上数字和最小,返回最小值

2、算法原理

a状态表示方程

小技巧:经验+题目要求

用一个二维数组表示,创建一个二维数组

dp[i][j]  表示当前从起点到当前节点的最小值

b状态转移方程

一个小技巧:找到最近的一步,划分问题

能到达dp[i][j]的只有一条路径,上或者左边,选择一个两者较小的值。因为dp[i-1][j]或者dp[i][j-1]也是表示他那个节点对路径最小值——问题进入闭环

dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]

c初始化

以下面这张图为例,为了避免越界访问我们本来应该在1,1的位置开始遍历的。给第一行和第一列进行初始化。

为了简化这个过程,我们给它多创建一行多创建一列,再给里面赋上合适的值这样避免了越界访问,也避免了初始化繁琐的操作,我们可以直接进行填表。

既然要选取较小值,那我们就直接弄上最大值INT_MAX,然后在0,1和1,0的位置附上0就行了,这样dp[1][1]就能保证刚好就是grid[0][0],这样从1开始的每一列都是获取上面的路径和,每一行都是获取左边的路径和,这样就是合理的赋值。

这其实就是运用了虚拟节点来进行初始化,简化初始化的行为。

这种方法需要注意两点:

  1. 进行合理赋值,保证后面填表的值是正确的
  2. 注意取值的下标映射

因为我们的dp表是多了一行多了一列,我们需要i-1,j-1才能取到正确的值

d填表顺序

从左到右,从上到下

e返回值

dp[m][n]

3、代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
            //建dp表
            //初始化
            //填表
            //返回值
            int m=grid.size();
            int n=grid[0].size();
            vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
            dp[0][1]=0;
            dp[1][0]=0;
            for(int i=1;i<=m;i++){
                for(int j=1;j<=n;j++){
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
                }
            }
            return dp[m][n];
    }
};

二、地下城游戏

1、题目解析

 这道题相较于第一题多了负数,但是还是有可以一样的处理——进行相加,并且还多了一个限制条件,骑士的值不能为零。也是只能向下和向右走。不过这道题需要返回骑士需要救到公主所需最低的健康值。

2、算法原理

a状态表示方程

经验+题目要求

有两种解题方式:

1、以某个位置为结尾。。。。。

假设dp[i][j]表示从期待您出发到达i,j位置数所需的最低健康点数

这个思路其实是错误的,因为你不仅需要进入这个房间,还要静茹下一个房间,这就导致了你不能简单的通过这个房间的前一步进行判断,还需要考虑后续房间的影响。————有后效性

2、以某个位置为起点。。。。。

dp[i][j]表示从这李出发到达终点所需最低初始健康。

b状态转移方程

根据最近的一步,划分问题

假设进入d[i][j]这个房间所需最小生命值为x

其实想要右边房间的话就需要:x+d[i][j]>=dp[i][j+1]

x>=dp[i][j+1]-d[i][j]

还有一种特殊情况需要我们考虑如果房间里面是一个较大血包的话,dp[i][j+1]-d[i][j]是有可能小于0的————这表示你就算是负多少多少都能够走到终点,但这是不合理的,负数骑士都死掉了。

所以

c初始化

虚拟节点(处理边界问题的好方法)

这道题需要考虑边界问题是最后一行和最后一列。

需要注意的两点:

1、设置合适的值,保证填表时值的正确性

走出迷宫最少得剩下一滴血

2、注意下标映射

因为是添加在最后一行和最后一列,不需要考虑下标问题

d填表顺序

从下往上,从右往左

e返回值

dp[0][0]

3、代码

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        //建表
        //初始化
        //填表
        //返回值
        int m=dungeon.size(),n=dungeon[0].size();
        vector<vector<int>> dp(m+1,vector<int> (n+1,INT_MAX));
        dp[m][n-1]=1;
        dp[m-1][n]=1;
        for(int i=m-1;i>=0;i--)
        {
            for(int j=n-1;j>=0;j--){
                int t=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
                dp[i][j]=max(1,t);
            }
        }
        return dp[0][0];
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/514820.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

(4)(4.6) Triducer

文章目录 前言 1 安装triducer 2 故障排除 3 参数说明 前言 Triducer 集速度、温度和深度传感器于一体。埃文在这篇 ardupilot.org 博文底部提供了这些说明(Evan at the bottom of this ardupilot.org blog post)。 1 安装triducer 下面的示例提供了在 Pixhawk 上安装 tri…

javaWeb城市公交查询系统的设计与实现

一、选题背景 随着低碳生活的普及&#xff0c;人们更倾向于低碳环保的出行方式&#xff0c;完善公交系统无疑具有重要意义。公交是居民日常生活中最常使用的交通工具之一&#xff0c;伴随着我国经济繁荣和城市人口增长&#xff0c;出行工具的选择也变得越来越重要。政府在公共…

使用vuepress搭建个人的博客(一):基础构建

前言 vuepress是一个构建静态资源网站的库 地址:VuePress 一般来说,这个框架非常适合构建个人技术博客,你只需要把自己写好的markdown文档准备好,完成对应的配置就可以了 搭建 初始化和引入 创建文件夹press-blog npm初始化 npm init 引入包 npm install -D vuepress…

涂鸦 IoT 开发平台产品开发使用教程

产品开发 一、涂鸦 IoT 平台 地址。 什么是涂鸦 IoT 开发平台&#xff1f; 涂鸦 IoT 开发平台支持海量物联网&#xff08;IoT&#xff09;设备、网关、服务、应用连接上云。在 产品开发 阶段&#xff0c;涂鸦 IoT 开发平台提供了多种连接方式&#xff0c;实现设备与 Io…

最新梨花带雨网页音乐播放器

源码简介 最新梨花带雨网页音乐播放器二开优化修复美化版全开源版本源码下载 梨花带雨播放器基于thinkphp6开发的XPlayerHTML5网页播放器前台控制面板,支持多音乐平台音乐解析。二开内容&#xff1a;修复播放器接口问题&#xff0c;把接口本地化&#xff0c;但是集成外链播放…

【系统架构师】-软件架构评估

1、质量属性 1、性能 系统的响应能力&#xff0c;响应时间、吞吐量&#xff0c; 策略&#xff1a;优先级队列、资源调度 2、可用性 系统正常运行的时间比例&#xff08;两次故障之间的时间长度&#xff09;&#xff0c;故障间隔时间&#xff0c; 策略&#xff1a;冗余、心…

JavaScript基础代码练习之翻转数组

一、要求将给定数组 [red, green, blue, pink, purple] 的内容反转存放&#xff0c;并将结果输出到控制台。 二、编写代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" cont…

【漏洞复现】通天星CMSV6车载主动安全监控云平台inspect_file接口处存在任意文件上传漏洞

免责声明&#xff1a;文章来源互联网收集整理&#xff0c;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;所产生的一切不良后果与文章作者无关。该…

深度学习评价指标(1):目标检测的评价指标

1. 简述 在计算机视觉/深度学习领域&#xff0c;每一个方向都有属于自己的评价指标。通常在评估一个模型时&#xff0c;只需要计算出相应的评价指标&#xff0c;便可以评估算法的性能。同时&#xff0c;所谓SOTA&#xff0c;皆是基于某一评价指标进行的评估。 接下来&#xff0…

如何通过Elasticsearch实现搜索的关键词达到高亮的效果

高亮 首先介绍一下什么是搜索的关键词达到高亮的效果&#xff0c;如图所示 当在百度里面搜索elasticsearch的时候&#xff0c;可以看到出现的搜索结果里面elasticsearch这个关键词明显与其他的条文不一样&#xff0c;用红颜色凸显了“高亮效果”。当我们想要在自己的项目里面…

基于JSP的农产品供销服务系统

背景 互联网的迅猛扩张彻底革新了全球各类组织的运营模式。自20世纪90年代起&#xff0c;中国的政府机关和各类企业便开始探索利用网络系统来处理管理事务。然而&#xff0c;早期的网络覆盖范围有限、用户接受度不高、互联网相关法律法规不完善以及技术开发不够成熟等因素&…

JMM内存模型 volatile关键字解析

前言 对于多线程等等的各种操作,相比各位都了然于胸,现在我们来介绍一下更底层一点点的JMM内存模型,其实也是一个很简单的理想的内存模型 注意与JVM的内存模型区分 多线程内存模型主要是基于CPU缓存搭建起来的 这里就区分工作内存和主内存了 我们线程操作的其实是主内存的一个副…

【WEEK6】 【DAY3】MySQL函数【中文版】

2024.4.3 Wednesday 目录 5.MySQL函数5.1.常用函数5.1.1.数据函数5.1.2.字符串函数5.1.2.1.CHAR_LENGTH(str)计算字符串str长度5.1.2.2.CONCAT(str1,str2,...)拼接字符串str1 str2 ...5.1.2.3.INSERT(str,pos,len,newstr)把原文str第pos位开始长度为len的字符串替换成newstr5.…

Springboot传参要求

传参的参数名称必须与Set方法的参数名字相同 &#xff0c;不然会报错。

PAC的启用与构建

PAC如何启用?构建PAC的编译选项控制&#xff1f;本博客探讨这几个问题。

【局部路径规划算法】—— DWA动态窗口法(c++实现))

参考资料&#xff1a; &#xff08;1&#xff09;机器人局部避障的动态窗口法(dynamic window approach) &#xff08;2&#xff09;机器人局部避障的动态窗口法 &#xff08;3&#xff09;局部规划算法&#xff1a;DWA算法原理 &#xff08;4&#xff09;SLAM学习&#xff1a;…

Android Monkey自动化测试

monkey一般用于压力测试&#xff0c;用户模拟用户事件 monkey 基本用法 adb shell monkey [参数] [随机事件数]monkey常用命令 -v&#xff1a;用于指定反馈信息级别&#xff0c;总共分三个等级-v -v -vadb shell mokey -v -v -v 100-s&#xff1a;用于指定伪随机数生成器的种…

安卓MT管理器v2.15.1

软件介绍 MT管理器是一款强大的文件管理工具和APK逆向修改神器。如果你喜欢它的双窗口操作风格&#xff0c;可以单纯地把它当成文件管理器使用。如果你对修改APK有深厚的兴趣&#xff0c;那么你可以用它做许许多多的事&#xff0c;例如汉化应用、替换资源、修改布局、修改逻辑…

相交链表 - LeetCode 热题 22

大家好&#xff01;我是曾续缘&#x1f4a4; 今天是《LeetCode 热题 100》系列 发车第 22 天 链表第 1 题 ❤️点赞 &#x1f44d; 收藏 ⭐再看&#xff0c;养成习惯 相交链表 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果…

CVE-2021-30517:Type confusion bug in LoadSuperIC

前言 这个漏洞是一个比较老的洞&#xff0c;之所以分析这个漏洞&#xff0c;只要是想再学习一下 ICs 相关的知识。并该漏洞的利用是利用与 String/Function 之间的混淆&#xff0c;比较有意思。 环境搭建 sudo apt install python git checkout 7d5e5f6c62c3f38acee12dc4114…