算法沉淀——动态规划之路径问题(leetcode真题剖析)

在这里插入图片描述

算法沉淀——动态规划之路径问题

  • 01.不同路径
  • 02.不同路径 II
  • 03.珠宝的最高价值
  • 04.下降路径最小和
  • 05.最小路径和
  • 06.地下城游戏

01.不同路径

题目链接:https://leetcode.cn/problems/unique-paths/

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

示例 1:

输入:m = 3, n = 7
输出:28

示例 2:

输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3:

输入:m = 7, n = 3
输出:28

示例 4:

输入:m = 3, n = 3
输出:6

提示:

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109

思路

这是一个典型的动态规划问题。以下是解题的一般步骤:

  1. 状态表示: 对于路径类问题,有两种状态表示方式,选择其中之一。这里选择从起始位置出发,到达 [i, j] 位置的方式:

    dp[i][j] 表示从起始位置到达 [i, j] 位置的路径数。

  2. 状态转移方程: 分析从 [i, j] 位置出发的一小步,有两种情况:

    • [i-1, j] 位置向下走一步,转移到 [i, j] 位置;
    • [i, j-1] 位置向右走一步,转移到 [i, j] 位置。

    因此,状态转移方程为:dp[i][j] = dp[i-1][j] + dp[i][j-1]

  3. 初始化:dp 数组前添加一行和一列,初始化 dp[0][1] 位置为 1

  4. 填表顺序: 从上往下,每一行从左往右填写。

  5. 返回值: 返回 dp[m][n] 的值,表示从起始位置到达终点位置的路径数。

代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        dp[1][1]=1;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(i==1&&j==1) continue;
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};

02.不同路径 II

题目链接:https://leetcode.cn/problems/unique-paths-ii/

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

网格中的障碍物和空位置分别用 10 来表示。

示例 1:

输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2:

输入:obstacleGrid = [[0,1],[0,0]]
输出:1 

提示:

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j]01

思路

根据上题分析,这题如果某个位置 [i - 1, j] 或者 [i, j - 1] 上存在障碍物,说明从这两个位置到达 [i, j] 的路径是被阻挡的,因此在计算 dp[i][j](表示从起点到达 [i, j] 的路径数)时,可以直接将 dp[i][j] 设为零,其余同上题。

代码

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size(),n=obstacleGrid[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        dp[1][0]=1;
        for(int i=1;i<=m;++i)
            for(int j=1;j<=n;++j)
                if(obstacleGrid[i-1][j-1]==0)
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
        return dp[m][n];
    }
};

03.珠宝的最高价值

题目链接:https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/

现有一个记作二维矩阵 frame 的珠宝架,其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为:

  • 只能从架子的左上角开始拿珠宝
  • 每次可以移动到右侧或下侧的相邻位置
  • 到达珠宝架子的右下角时,停止拿取

注意:珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝,比如 frame = [[0]]

示例 1:

输入: frame = [[1,3,1],[1,5,1],[4,2,1]]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最高价值的珠宝

提示:

  • 0 < frame.length <= 200
  • 0 < frame[0].length <= 200

思路

在处理这类问题时,动态规划的状态表可以采用两种主要形式:一是从某个位置出发,描述到达其他位置的情况;二是从起始位置到达某个位置,描述达到该位置时的状态。在这里,我们选择第二种方式定义状态表:

我们使用 dp[i][j] 表示从起始位置到达 [i, j] 位置时的最大价值。在考虑到达 [i, j] 的两种方式时,即从上方 [i - 1, j] 或从左侧 [i, j - 1] 到达,我们需要选择其中最大价值的路径。因此,状态转移方程为:

dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];

在初始化过程中,可以添加一个辅助结点,并将所有值初始化为零。填表的顺序是从上往下逐行填写,每一行从左往右。最后,我们应该返回 dp[m][n] 的值,表示在整个网格中的最大价值。

代码

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m=frame.size(),n=frame[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));

        for(int i=1;i<=m;++i)
            for(int j=1;j<=n;++j)
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
        
        return dp[m][n];
    }
};

04.下降路径最小和

题目链接:https://leetcode.cn/problems/minimum-falling-path-sum/

给你一个 n x n方形 整数数组 matrix ,请你找出并返回通过 matrix下降路径最小和

下降路径 可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左或者向右的第一个元素)。具体来说,位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)(row + 1, col) 或者 (row + 1, col + 1)

示例 1:

输入:matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出:13
解释:如图所示,为和最小的两条下降路径

示例 2:

输入:matrix = [[-19,57],[-40,-5]]
输出:-59
解释:如图所示,为和最小的下降路径

提示:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 100
  • -100 <= matrix[i][j] <= 100

在处理这种「路径类」的问题时,动态规划的状态表一般有两种常见形式:一是从某个位置出发,描述到达其他位置的情况;二是从起始位置到达某个位置,描述达到该位置时的状态。在这里,我们选择第二种方式定义状态表:

我们使用 dp[i][j] 表示到达 [i, j] 位置时,所有下降路径中的最小和。在考虑到达 [i, j] 的三种方式时,即从正上方 [i - 1, j]、左上方 [i - 1, j - 1] 和右上方 [i - 1, j + 1] 转移到 [i, j] 位置,我们需要选择三者中的最小值,再加上矩阵在 [i, j] 位置的值。因此,状态转移方程为:

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

在初始化过程中,我们添加一个辅助结点,将其值初始化为正无穷大,以保证后续填表时是正确的。同时,需要注意下标的映射关系。在本题中,我们添加了一行和两列,将第一行的值初始化为 0。填表的顺序是从上往下逐行填写。最后,我们不是返回 dp[m][n] 的值,而是返回 dp 表中最后一行的最小值,因为题目要求只要到达最后一行即可。

代码

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int m=matrix.size(),n=matrix[0].size();
        vector<vector<int>> dp(n+1,vector<int>(n+2,INT_MAX));
        for(int i=0;i<n+2;i++) dp[0][i]=0;

        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dp[i][j]=matrix[i-1][j-1]+min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1]));
        
        int ret=INT_MAX;
        for(int i=1;i<=n;i++)
            ret=min(ret,dp[n][i]);

        return ret;
    }
};

05.最小路径和

题目链接:https://leetcode.cn/problems/minimum-path-sum/

给定一个包含非负整数的 *m* x *n* 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

**说明:**每次只能向下或者向右移动一步。

示例 1:

输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。

示例 2:

输入:grid = [[1,2,3],[4,5,6]]
输出:12

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200

思路

在处理这种路径类问题时,我们通常选择两种状态表现形式:一是从某个位置出发,描述到达其他位置的情况;二是从起始位置到达某个位置,描述达到该位置时的状态。在这里,我们选择第二种方式定义状态表:

我们使用 dp[i][j] 表示到达 [i, j] 位置处的最小路径和。在分析 dp[i][j] 的情况时,我们考虑到达 [i, j] 位置之前的一小步有两种情况:一是从上方 [i - 1, j] 向下走一步,转移到 [i, j] 位置;二是从左方 [i, j - 1] 向右走一步,转移到 [i, j] 位置。由于我们要找的是最小路径,因此只需要这两种情况下的最小值,再加上 [i, j] 位置上本身的值即可。

也就是说,状态转移方程为:dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];

在初始化过程中,我们可以在最前面加上一个「辅助结点」,帮助我们初始化。使用这种技巧需要注意两个点:一是辅助结点里面的值要保证后续填表是正确的;二是下标的映射关系。在本题中,添加了一行和一列,所有位置的值可以初始化为无穷大,然后让 dp[0][1] = dp[1][0] = 1 即可。

填表的顺序是从上往下逐行填写,每一行从左往右。最后,我们返回 dp 表中最后一个位置的值,即 dp[m][n]

代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
        dp[0][1]=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];
    }
};

06.地下城游戏

题目链接:https://leetcode.cn/problems/dungeon-game/

恶魔们抓住了公主并将她关在了地下城 dungeon右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。

有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。

为了尽快解救公主,骑士决定每次只 向右向下 移动一步。

返回确保骑士能够拯救到公主所需的最低初始健康点数。

**注意:**任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。

示例 1:

输入:dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出:7
解释:如果骑士遵循最佳路径:右 -> 右 -> 下 -> 下 ,则骑士的初始健康点数至少为 7 。

示例 2:

输入:dungeon = [[0]]
输出:1 

提示:

  • m == dungeon.length
  • n == dungeon[i].length
  • 1 <= m, n <= 200
  • -1000 <= dungeon[i][j] <= 1000

思路

这道题可以通过动态规划求解,首先需要定义状态表现形式。如果我们定义为“从起点开始,到达 [i, j] 位置的时候,所需的最低初始健康点数”,分析状态转移时可能会受到后续路径的影响。因此,更合适的状态表现形式是“从 [i, j] 位置出发,到达终点时所需要的最低初始健康点数”。

综上,我们定义状态表达为:dp[i][j]表示:从 [i, j] 位置出发,到达终点时所需的最低初始健康点数。

在状态转移方程中,我们考虑从 [i, j] 位置出发的两种选择: i. 向右走到终点,即从 [i, j] 到 [i, j + 1]; ii. 向下走到终点,即从 [i, j] 到 [i + 1, j]。

对于这两种选择,我们需要选择使得到达终点时的初始健康点数最小的路径。因此,状态转移方程为: dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];

然而,由于 dungeon[i][j] 可能是一个较大的正数,计算得到的dp[i][j]的值可能会小于等于 0。如果初始健康点数小于等于 0,马上死亡,因此我们需要处理这种情况,将 dp[i][j] 与 1 取最大值:dp[i][j]=max(1,dp[i][j]);

在初始化阶段,我们在最前面加上一个“辅助结点”来帮助初始化,需要注意辅助结点里面的值要保证后续填表是正确的,以及下标的映射关系。在本题中,我们在 dp 表的最后一行和最后一列分别添加一行和一列,将所有的值初始化为无穷大,然后让 dp[m][n - 1] = dp[m - 1][n] = 1

填表的顺序是从下往上逐行填写,每一行从右往左。最后,我们返回 dp[0][0] 的值。

代码

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]=dp[m-1][n]=1;

        for(int i=m-1;i>=0;i--)
            for(int j=n-1;j>=0;j--)
            {
                dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
                dp[i][j]=max(1,dp[i][j]);
            }
        
        return dp[0][0];
    }
};

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

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

相关文章

c++: 用c++语言对车辆进行建模

一 原理 1.1 阿克曼转向模型 转向半径:后轴中心点到原点O的距离 已知道转向半径,可以反求转向角。或者知道转向角,可以求出转向半径。 四个顶点的转向半径。 还要定义这两个参数 1.2 车辆运动的建模 运动写在大的while循环里。 绘制车辆的思路;(1)清

020 基于Spring Boot + Thymeleaf 实现的任务发布网站(源码+数据库)

部分代码地址&#xff1a; https://github.com/XinChennn/xc020-springboot-recruit 基于Spring Boot Thymeleaf 实现的任务发布网站&#xff08;源码数据库&#xff09; 一、系统介绍 雇主&#xff1a;登录、注册、发布任务、选择中标雇员、评价雇员雇员&#xff1a;登录、…

如何解决Nginx启动出现闪退问题?

哈喽&#xff0c;大家好&#xff0c;我是小浪。那么大家首次在启动nginx的时候&#xff0c;绝大部分同学会出现以下情况&#xff0c;就是我们双击nginx.exe文件之后&#xff0c;屏幕闪退一下就没了&#xff0c;然后我们访问localhost:8080提示404. 那么出现这种情况其实是我们…

【深度学习笔记】 3_13 丢弃法

注&#xff1a;本文为《动手学深度学习》开源内容&#xff0c;部分标注了个人理解&#xff0c;仅为个人学习记录&#xff0c;无抄袭搬运意图 3.13 丢弃法 除了前一节介绍的权重衰减以外&#xff0c;深度学习模型常常使用丢弃法&#xff08;dropout&#xff09;[1] 来应对过拟合…

“点击查看显示全文”遇到的超链接默认访问的问题

今天在做一个例子&#xff0c;就是很常见的点击展开全文。 我觉得这是一个很简单的效果&#xff0c;也就几行代码的事&#xff0c;结果点击了以后立刻隐藏不见&#xff0c;控制台代码也不报错&#xff0c;耽误了我很长时间&#xff0c;最后才发现问题出在超链接身上。 “展开全…

k8s-kubeapps部署 20

部署kubeapps应用&#xff0c;为Helm提供web UI界面管理&#xff1a; 下载最新版本的kubeapps并修改其values.yaml文件 下载并拉取所需镜像&#xff1a; 部署应用 添加解析 修改svc暴露方式为LoadBalancer 得到分配地址 访问http://192.168.182.102 授权并获取token 1.24前的…

osmnx笔记:从OpenStreetMap中提取点和边的shp文件(FMM文件准备内容)

1 导入库 import osmnx as ox import time from shapely.geometry import Polygon import os import numpy as np 2 提取Openstreetmap 的graph Gox.graph_from_place(Huangpu,Shanghai,China,network_typedrive,simplifyTrue) ox.plot_graph(G) 3 提取graph中的点和边 gdf…

pytest如何在类的方法之间共享变量?

在pytest中&#xff0c;setup_class是一个特殊的方法&#xff0c;它用于在类级别的测试开始之前设置一些初始化的状态。这个方法会在类中的任何测试方法执行之前只运行一次。 当你在setup_class中使用self来修改类属性时&#xff0c;你实际上是在修改类的一个实例属性。在Pyth…

《模仿游戏》:天才团队如何破解密码学之谜

引言 计算机科学相关的电影不少&#xff0c;有探索人工智能的《黑客帝国》、还有逻辑和结构学的《盗梦空间》、还有互联网创业的《社交网络》和《硅谷海盗》、还有探索虚拟世界的《源代码》&#xff0c;更甚有国产计算机科学科幻启蒙儿童电视剧《快乐星球》。上述电影充满科技和…

函数——递归6(c++)

角谷猜想 题目描述 日本一位中学生发现一个奇妙的 定理&#xff0c;请角谷教授证明&#xff0c;而教授 无能为力&#xff0c;于是产生了角谷猜想。 猜想的内容&#xff1a;任给一个自然数&#xff0c; 若为偶数则除以2&#xff0c;若为奇数则乘 3加1&#xff0c;得到一个新的…

JDK8新特性全解析:Java8变革之旅

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

云原生之容器编排实践-ruoyi-cloud项目部署到K8S:MySQL8

背景 前面搭建好了 Kubernetes 集群与私有镜像仓库&#xff0c;终于要进入服务编排的实践环节了。本系列拿 ruoyi-cloud 项目进行练手&#xff0c;按照 MySQL &#xff0c; Nacos &#xff0c; Redis &#xff0c; Nginx &#xff0c; Gateway &#xff0c; Auth &#xff0c;…

测试圈的网红工具:Jmeter到底难在哪里?!

小欧的公司最近推出了一款在线购物应用&#xff0c;吸引了大量用户。然而随着用户数量的增加&#xff0c;应用的性能开始出现问题。用户抱怨说购物过程中页面加载缓慢&#xff0c;甚至有时候无法完成订单&#xff0c;小欧作为负责人员迫切需要找到解决方案。 在学习JMeter之前…

[VNCTF2024]-Web:CheckIn解析

查看网页 一款很经典的游戏&#xff0c;而且是用js写的 在调试器里面我们可以看见&#xff0c;如果游戏通关的话&#xff0c;它会进行一系列操作&#xff0c;包括使用console.log(_0x3d9d[0]);输出_0x3d9d[0]到控制台&#xff0c;那我们就直接在点击在控制台求出它的值

基于SpringBoot实现的医院药品管理系统

一、系统架构 前端&#xff1a;html | layui | js | css 后端&#xff1a;springboot | mybatis-plus 环境&#xff1a;jdk1.6 | mysql | maven 二、代码及数据库 三、功能介绍 01. 登录页 02. 药品库存管理-登记出入口信息 03. 药品库存管理-问题药品信息 …

软考45-上午题-【数据库】-数据操纵语言DML

一、INSERT插入语句 向SQL的基本表中插入数据有两种方式&#xff1a; ①直接插入元组值 ②插入一个查询的结果值 1-1、直接插入元组值 【注意】&#xff1a; 列名序列是可选的&#xff0c;若是所有列都要插入数值&#xff0c;则可以不写列名序列。 示例&#xff1a; 1-2、插…

基于ZYNQ的PCIE高速数据采集卡的设计(二)总体设计与上位机

采集卡总体设计及相关技术 2.1 引言 本课题是来源于雷达辐射源识别项目&#xff0c;需要对雷达辐射源中频信号进行采集传输 和存储。本章基于项目需求&#xff0c;介绍采集卡的总体设计方案。采集卡设计包括硬件设计 和软件设计。首先对采集卡的性能和指标进行分析&#x…

ELK 简介安装

1、概念介绍 日志介绍 日志就是程序产生的&#xff0c;遵循一定格式&#xff08;通常包含时间戳&#xff09;的文本数据。 通常日志由服务器生成&#xff0c;输出到不同的文件中&#xff0c;一般会有系统日志、 应用日志、安全日志。这些日志分散地存储在不同的机器上。 日志…

如何使用移动端设备在公网环境远程访问本地黑群晖

文章目录 前言本教程解决的问题是&#xff1a;按照本教程方法操作后&#xff0c;达到的效果是前排提醒&#xff1a; 1. 搭建群晖虚拟机1.1 下载黑群晖文件vmvare虚拟机安装包1.2 安装VMware虚拟机&#xff1a;1.3 解压黑群晖虚拟机文件1.4 虚拟机初始化1.5 没有搜索到黑群晖的解…

深度学习500问——Chapter01:数学基础

文章目录 前言 1.1 向量和矩阵 1.1.1 标量、向量、矩阵、张量之间的联系 1.1.2 张量与矩阵的区别 1.1.3 矩阵和向量相乘结果 1.1.4 向量和矩阵的范数归纳 1.1.5 如何判断一个矩阵为正定 1.2 导数和偏导数 1.2.1 导数偏导计算 1.2.2 导数和偏导数有什么区别 1.3 特征值和特征向量…
最新文章