动态规划 之 路径问题 算法专题

一. 不同路径

不同路径

  1. 状态表示
    dp[i][j] 表示走到[i][j]位置, 有几种不同的路径
  2. 状态转移方程
    以离[i][j] 最近的位置划分问题
    1.从[i - 1][j] 到[i][j], 到[i][j]位置的不同路径数 就是和 到[i - 1][j]位置的不同路径数相同, 即dp[i][j] = dp[i - 1][j]
    2.从[i][j - 1] 到[i][j], 到[i][j]位置的不同路径数 就是和 到[i ][j - 1]位置的不同路径数相同, 即dp[i][j] = dp[i][j - 1]
  • dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

  1. 初始化
    使用优化的思想进行初始化, 添加虚拟节点
    在第一行和第一列的位置填表时会发生越界
    所以需要添加一行一列
    在这里插入图片描述
    我们只需要像上表一样初始化虚拟节点, 就可以正确的进行填表

  2. 填表顺序
    从上往下 从左往右

  3. 返回值
    返回dp[m][n]

class Solution {
    public int uniquePaths(int m, int n) {
        //1. 创建表
        //2. 初始化
        //3. 填表
        //4. 返回值
        int[][] dp = new int[m + 1][n + 1];
      
        dp[0][1] = 1;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
}

二. 不同路径II

不同路径II

  1. 状态表示
    dp[i][j] 表示走到[i][j]位置, 有几种不同的路径
  2. 状态转移方程
    以离[i][j] 最近的位置划分问题
    1.从[i - 1][j] 到[i][j], 到[i][j]位置的不同路径数 就是和 到[i - 1][j]位置的不同路径数相同, 即dp[i][j] = dp[i - 1][j]
    2.从[i][j - 1] 到[i][j], 到[i][j]位置的不同路径数 就是和 到[i ][j - 1]位置的不同路径数相同, 即dp[i][j] = dp[i][j - 1]
    但是如果此时的[i][j]是障碍物, 那么到达这个位置的路径数就为0, 所以dp[i][j] = 0
  • dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

  1. 初始化
    使用优化的思想进行初始化, 添加虚拟节点
    在第一行和第一列的位置填表时会发生越界
    所以需要添加一行一列
    在这里插入图片描述
    我们只需要像上表一样初始化虚拟节点, 就可以正确的进行填表

  2. 填表顺序
    从上往下 从左往右

  3. 返回值
    返回dp[m][n]

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
         //1. 创建表
        //2. 初始化
        //3. 填表
        //4. 返回值
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m + 1][n + 1];
  
        dp[0][1] = 1;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(obstacleGrid[i - 1][j - 1] == 1) {
                    dp[i][j] = 0;
                }else{
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}

三. 珠宝的最高价值

珠宝的最高价值

  1. 状态表示
    dp[i][j] 表示走到[i][j]位置, 获得的珠宝的最高价值是多少
  2. 状态转移方程
    以离[i][j] 最近的位置划分问题
    到[i][j]位置的获得的珠宝的最高价值 就是到[i - 1][j]位置的获得的珠宝的最高价值 与 到[i][j - 1]位置的获得的珠宝的最高价值 的最大值, 然后加上[i][j]位置本来的价值
  • dp[i][j] = max(dp[i - 1][j] + dp[i][j - 1]) + frame[i - 1][j - 1](采用优化的思想, 与原下标对应要 - 1)
  1. 初始化
    使用优化的思想进行初始化, 添加虚拟节点
    在第一行和第一列的位置填表时会发生越界
    所以需要添加一行一列
    我们只需要将虚拟节点都设为0即可
  2. 填表顺序
    从上往下 从左往右
  3. 返回值
    返回dp[m][n]
class Solution {
    public int jewelleryValue(int[][] frame) {
        //1. 创建dp
        //2. 初始化
        //3. 填表
        //4. 返回值
        int m = frame.length;
        int n = frame[0].length;
        int[][] dp = new int[m + 1][n + 1];
   
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
}

四. 下降路径最小和

下降路径最小和

  1. 状态表示
    dp[i][j] 表示走到[i][j]位置, 路径的最小和
  2. 状态转移方程
    以离[i][j] 最近的位置划分问题
    到[i][j]位置的路径的最小和 就是到[i - 1][j - 1]位置路径的最小和 与 到[i - 1][j]位置路径的最小和 与 [i - 1][j + 1]位置路径的最小和 的最小值, 然后加上[i][j]位置本来的值
  • dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i - 1][j - 1](采用优化的思想, 与原下标对应要 - 1)
  1. 初始化
    使用优化的思想进行初始化, 添加虚拟节点
    在第一行和第一列和最后一列的位置填表时会发生越界
    所以需要添加一行两列
    我们需要将虚拟节点都设为最大值, 防止对原来的数进行干扰
  2. 填表顺序
    从上往下 从左往右
  3. 返回值
    返回最后一行中的最小值
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        //1. 创建dp
        //2. 初始化
        //3. 填表
        //4. 返回值
        int n = matrix.length;
        int[][] dp = new int[n + 1][n + 2];
        for(int i = 1; i <= n; i++){
            dp[i][0] = Integer.MAX_VALUE;
            dp[i][n + 1] = Integer.MAX_VALUE;
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i - 1][j - 1];
            }
        }
        int min = Integer.MAX_VALUE;
        for(int j = 1; j <= n; j++){
            min = Math.min(min, dp[n][j]);
        }
        return min;
    }
}

五. 最小路径和

最小路径和

  1. 状态表示
    dp[i][j] 表示走到[i][j]位置, 路径的最小和
  2. 状态转移方程
    以离[i][j] 最近的位置划分问题
    到[i][j]位置的路径的最小和 就是到[i - 1][j]位置路径的最小和 与 [i][j - 1]位置路径的最小和 的最小值, 然后加上[i][j]位置本来的值
  • dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1](采用优化的思想, 与原下标对应要 - 1)
  1. 初始化
    使用优化的思想进行初始化, 添加虚拟节点
    在第一行和第一列的位置填表时会发生越界
    所以需要添加一行一列
    我们需要将虚拟节点设为最大值, 但是[0][1]位置的值要设为0, 防止对原来的数进行干扰
  2. 填表顺序
    从上往下 从左往右
  3. 返回值
    dp[m][n]
class Solution {
    public int minPathSum(int[][] grid) {
        // 1. 创建dp
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = Integer.MAX_VALUE;
        }
        dp[0][1] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
}

六. 地下城游戏

地下城游戏

  1. 状态表示
    dp[i][j] 如果表示走到[i][j]位置, 所需要的最小血量, 是没办法完成这道题的, 因为, 每走一步, 所需的最小血量都在更新
    所以dp[i][j] 表示从[i][j]位置开始, 所需要的最小血量
  2. 状态转移方程
    以离[i][j] 最近的位置划分问题
    1.[i][j]位置所需要的最小血量 + [i][j]位置需要加或减的血量 一定是要 >= 到[i + 1][j]位置所需要的最小血量, 才能保证走下一个位置的时候不会死, 所以dp[i][j] = dp[i + 1][j] - 原表的[i][j]
    2.[i][j]位置所需要的最小血量 + [i][j]位置需要加或减的血量 一定是要 >= 到[i][j + 1]位置所需要的最小血量, 才能保证走下一个位置的时候不会死, 所以dp[i][j] = dp[i][j + 1] - 原表的[i][j]
  • dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - 原表的[i][j]
    但是我们得出的dp[i][j] 必须是>0的, 如果<0, 就设为1, 所需要的最低血量
  1. 初始化
    使用优化的思想进行初始化, 添加虚拟节点
    在最后一行和最后一列的位置填表时会发生越界
    所以需要添加一行一列
    我们需要将虚拟节点设为最大值, 但是[m][n - 1]位置 和[m - 1][n]位置 的值要设为1, 所需要的最低血量
  2. 填表顺序
    从下往上 从右往左
  3. 返回值
    dp[0][0]
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
          // 1. 创建dp
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m = dungeon.length;
        int n = dungeon[0].length;
        int [][] dp = new int[m + 1][n + 1];
        for(int i = m; i >= 0; i--){
            dp[i][n] = Integer.MAX_VALUE;
        }
        for(int j = n; j >= 0; j--){
            dp[m][j] = Integer.MAX_VALUE;
        }
        dp[m][n - 1] = dp[m - 1][n] = 1;
        for(int i = m - 1; i >= 0; i--){
            for(int j = n - 1; j >=0; j--){
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = Math.max(1, dp[i][j]);
            }
        }
        return dp[0][0];
    }
}

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

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

相关文章

浮动路由：实现出口线路的负载均衡冗余备份。

浮动路由：实现出口线路的负载均衡冗余备份。

浮动路由 Tip&#xff1a;浮动路由指在多条默认路由基础上加入优先级参数&#xff0c;实现出口线路冗余备份。 ip routing-table //查看路由表命令 路由优先级参数&#xff1a;越小越优 本次实验测试两条默认路由&#xff0c;其中一条默认路由添加优先级参数&#xff0c;设置…
阅读更多...
补一下 二维 平面直角坐标系 到三维

补一下 二维 平面直角坐标系 到三维

上一篇帖子写到 二维的平面直角坐标系&#xff0c;是那样的&#xff0c;这次补充一下三维的。首先需要&#xff0c;安装一个包&#xff0c;如下&#xff1a; 然后&#xff0c;把参数输入&#xff0c;输入这个坐标系的参数&#xff0c;如下&#xff1a; 这样就可以输出如下的三…
阅读更多...
CertiK创始人顾荣辉出席新加坡商业与慈善论坛，发表主旨演讲并主持专题讨论

CertiK创始人顾荣辉出席新加坡商业与慈善论坛，发表主旨演讲并主持专题讨论

2024年11月5日 —— 美国哥伦比亚大学教授、CertiK联合创始人、MAS国际技术顾问顾荣辉受邀参加2024年度新加坡商业与慈善论坛&#xff08;Business & Philanthropy Leadership Forum Singapore&#xff0c;简称B&P Forum&#xff09;&#xff0c;期间发表主旨演讲并主持…
阅读更多...
基于STM32的智能物联网家用机器人设计

基于STM32的智能物联网家用机器人设计

引言 本项目基于STM32微控制器设计了一个智能物联网家用机器人&#xff0c;通过集成多个传感器模块、摄像头以及Wi-Fi模块&#xff0c;实现远程控制、家庭监控和环境数据采集等功能。该系统可以监测家中的环境状况&#xff0c;如温湿度、烟雾浓度等&#xff0c;还可以作为安全…
阅读更多...
jenkins流水线pipeline

jenkins流水线pipeline

创建项目 1. 新建item 并选择pipeline 1.1 和普通项目配置的区别 普通项目配置目录&#xff1a; pipeline项目目录&#xff1a; pipeline的两种语法 声明式语法 2. 配置 2.1 流水线配置 2.2 选择声明式 声明式需要添加一个名为Jenkinsfile的文件实现流水线 Jenkinsfile的…
阅读更多...
【CSS】标准怪异盒模型

【CSS】标准怪异盒模型

概念 CSS 盒模型本质上是一个盒子&#xff0c;盒子包裹着HTML 元素&#xff0c;盒子由四个属性组成&#xff0c;从内到外分别是&#xff1a;content 内容、padding 内填充、border 边框、外边距 margin 盒模型的分类 W3C 盒子模型(标准盒模型) IE 盒子模型(怪异盒模型) 两种…
阅读更多...
系统上云-流量分析和链路分析

系统上云-流量分析和链路分析

优质博文&#xff1a;IT-BLOG-CN 一、流量分析 【1】流量组成&#xff1a; 按协议划分&#xff0c;流量链路可分为HTTP、SOTP、QUIC三类。 HTTPSOTPQUIC场景所有HTTP请求&#xff0c;无固定场景国内外APP等海外APP端链路选择DNS/CDN(当前特指Akamai)APP端保底IP列表/动态IP下…
阅读更多...
linux操作系统的开机引导

linux操作系统的开机引导

一、linux操作系统的开机引导的过程 1、开机自检 根据bios的设置&#xff0c;对cpu&#xff0c;内存&#xff0c;显卡&#xff0c;键盘等设备进行初步检测&#xff0c;如果以上检测设备工作正常&#xff0c;系统会把控制权移交到硬盘 2、MBR引导/GPR引导 分区之后&#xff…
阅读更多...
【c++丨STL】vector的使用

【c++丨STL】vector的使用

&#x1f31f;&#x1f31f;作者主页&#xff1a;ephemerals__ &#x1f31f;&#x1f31f;所属专栏&#xff1a;C、STL 目录 前言 vector简要介绍 一、vector的默认成员函数 构造函数(constructor) 析构函数(destructor) 赋值运算符重载operator 二、vector的容量接口…
阅读更多...
[前端] 为网站侧边栏添加搜索引擎模块

[前端] 为网站侧边栏添加搜索引擎模块

前言 最近想给我的个人网站侧边栏添加一个搜索引擎模块&#xff0c;可以引导用户帮助本站SEO优化&#xff08;让用户可以通过点击搜索按钮完成一次对本人网站的搜索&#xff0c;从而实现对网站的搜索引擎优化&#xff09;。 最开始&#xff0c;我只是想实现一个简单的百度搜索…
阅读更多...
Git - 两种方式撤销已提交到远端仓库的记录并删除提交记录

Git - 两种方式撤销已提交到远端仓库的记录并删除提交记录

文章目录 命令行方式附 命令行方式 确定要撤销的提交记录 首先&#xff0c;使用以下命令查看提交历史&#xff1a; git log找到想撤销的提交记录的哈希值&#xff08;SHA&#xff09; &#xff0c;比如9c9c98d6f7f28c41d971f8efd51ed31f9720792c 撤销提交记录 根据需求选择以下…
阅读更多...
【命令执行waf绕过】

【命令执行waf绕过】

一、绕过空格 二、绕过黑名单 三、绕过长度限制 四、练习 发现了两个文件&#xff0c;cat读取&#xff0c;但是被过滤了&#xff1a; 用 I F S IFS IFS绕过读出index的源码&#xff0c;发现过滤了很多东西&#xff0c;黑名单过滤&#xff1a; 字符串拼接绕过&#xff1a; …
阅读更多...
Beans模块之工厂模块注解模块AnnotatedGenericBeanDefinition

Beans模块之工厂模块注解模块AnnotatedGenericBeanDefinition

博主介绍&#xff1a;✌全网粉丝5W&#xff0c;全栈开发工程师&#xff0c;从事多年软件开发&#xff0c;在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战&#xff0c;博主也曾写过优秀论文&#xff0c;查重率极低&#xff0c;在这方面有丰富的经验…
阅读更多...
【毫米波雷达（三）】汽车控制器启动流程——BootLoader

【毫米波雷达（三）】汽车控制器启动流程——BootLoader

汽车控制器启动流程——BootLoader 一、什么是Bootloader(BT)&#xff1f;二、FBL、PBL、SBL、ESS的区别三、MCU的 A/B分区的实现 一、什么是Bootloader(BT)&#xff1f; BT就是一段程序&#xff0c;一段引导程序。它包含了启动代码、中断、主程序等。 雷达启动需要由BT跳转到…
阅读更多...
原生鸿蒙的竞争力到底如何？

原生鸿蒙的竞争力到底如何？

目录 1. 崛起与挑战2. 安全机制3. 自动化检测前移4. 深入探讨开发者服务优势 1. 崛起与挑战 长期以来&#xff0c;移动操作系统市场被IOS和安卓所垄断&#xff0c;一直都难以推出完整的自主系统&#xff0c;面临诸多挑战&#xff0c;如推广困难、应用适配难度大&#xff0c;以及…
阅读更多...
Unity SRP学习笔记（二）

Unity SRP学习笔记（二）

Unity SRP学习笔记&#xff08;二&#xff09; 主要参考&#xff1a; https://catlikecoding.com/unity/tutorials/custom-srp/ https://docs.unity.cn/cn/2022.3/ScriptReference/index.html 中文教程部分参考&#xff08;可选&#xff09;&#xff1a; https://tuncle.blog/c…
阅读更多...
欧冠：拜仁进攻线持续飘红？

欧冠：拜仁进攻线持续飘红？

里斯本竞技最终4-1击败曼城&#xff0c;瓜迪奥拉的球队惨遭3连败。目前曼城的防线球员身体状态的确一般&#xff0c;一对一总是跟不上节奏&#xff0c;这也是曼城两次遭遇点球判罚的原因。当一个人失去希望时&#xff0c;眼神是空洞的&#xff0c;哈兰德下半场罚丢点球的时刻&a…
阅读更多...
从0开始的STM32之旅8 串口通信（II）

从0开始的STM32之旅8 串口通信（II）

目录 在开始理解底层原理之前&#xff0c;我们先尝试一下 怎么做 进一步理解 HAL_UART_Transmit HAL_UART_Receive 在开始理解底层原理之前&#xff0c;我们先尝试一下 现在我们综合一下&#xff0c;要求完成如下的事情&#xff1a; 在主程序中存在一个flag变量描述当前有…
阅读更多...
HarmonyOS使用arkTS拉起指定第三方应用程序

HarmonyOS使用arkTS拉起指定第三方应用程序

HarmonyOS使用arkTS拉起指定第三方应用程序 前言代码及说明bundleName获取abilityName获取 前言 本篇只说采用startAbility方式拉起第三方应用&#xff0c;需要用到两个必备的参数bundleName&#xff0c;abilityName&#xff0c;本篇就介绍如何获取参数… 代码及说明 bundle…
阅读更多...
WPF之iconfont（字体图标）使用

WPF之iconfont（字体图标）使用

1&#xff0c;前文&#xff1a; WPF的Xaml是与前端的Html有着高度相似性的标记语言&#xff0c;所以Xaml也可同Html一般轻松使用阿里提供的海量字体图标&#xff0c;从而有效的减少开发工作度。 2&#xff0c;下载字体图标&#xff1a; 登录阿里图标库网iconfont-阿里巴巴矢量…
阅读更多...
最新文章

Copyright @ 2022~2023