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

C++--动态规划路径问题

1.不同路径 力扣

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

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

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

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

示例 1:

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

示例 2:

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/unique-paths-ii

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

2.不同路径  力扣

一个机器人位于一个 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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/unique-paths

class Solution {
public:int uniquePaths(int m, int n) {//以某一处为结尾,创建dp表vector<vector<int>> dp(m+1,vector<int>(n+1));//初始化dp表//dp[0][1]=1;dp[1][0]=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];}
};

3.礼物的最大价值  力扣

在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?

示例 1:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof

class Solution {
public:int maxValue(vector<vector<int>>& grid) {int m=grid.size();int n=grid[0].size();vector<vector<int>> arr(m+1,vector<int>(n+1));//初始化,求最大,所以初始化最小,vector默认初始//化为0for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){arr[i][j]=max(arr[i-1][j],arr[i][j-1])+grid[i-1][j-1];//递推公式}}return arr[m][n];}
};

4.下降路径最小和  力扣

给你一个 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
解释:如图所示,为和最小的下降路径

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/minimum-falling-path-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

5.最小路径和   力扣

给定一个包含非负整数的 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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/minimum-path-sum

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int n=matrix.size();vector<vector<int>> dp(n+1,vector<int>(n+2,INT_MAX));//创建dp表,并初始化为最大值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]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1]))+matrix[i-1][j-1];//递推公式}}int ret=INT_MAX;for(int i=0;i<=n;i++)ret=min(ret,dp[n][i]);//找最小return ret;}
};
class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int r=grid.size();int l=grid[0].size();vector<vector<int>> dp(r+1,vector<int>(l+1,INT_MAX));//创建dp表,并初始化,找最小,初始化为最大dp[0][1]=dp[1][0]=0;//由于有两种走法,所以要求drid[0][0]的上方和左边的为最小数0for(int i=1;i<=r;i++){for(int j=1;j<=l;j++){dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];//地推公式}}return dp[r][l];//返回值}
};

6.地下城游戏  力扣

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

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

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

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

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

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

示例 1:

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

示例 2:

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/dungeon-game

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int r=dungeon.size();int l=dungeon[0].size();vector<vector<int>> dp(r+1,vector<int>(l+1,INT_MAX));//创建dp表+初始化dp[r][l - 1] = dp[r - 1][l] = 1;for(int i=r-1;i>=0;i--){for(int j=l-1;j>=0;j--){dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];//填表+递推公式if(dp[i][j]<=0)dp[i][j]=1;}}return dp[0][0];//返回值}
}

相关文章:

C++--动态规划路径问题

1.不同路径 力扣 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finish”&#xff09;。 现在考虑网格中有障碍物。那么从…...

从实践彻底掌握MySQL的主从复制

目录 一、本次所用结构如图---一主多从级联&#xff1a; 二、IP。 三、配置M1&#xff1a; 四、从库M1S1&#xff1a; 五、从库M2配置&#xff1a; 六、 从库M2S1&#xff1a; 一、本次所用结构如图--- 一主多从级联&#xff1a; 二、IP。这里M1S1和M1S2一样的&#xff0…...

机器学习深度学习——线性回归的基本元素

回归用来表示输入输出之间的关系。 用实际例子来解释一下线性回归&#xff1a;根据房屋的面积、房龄来估算房屋价格。为了实现这个预测放假的模型&#xff0c;需要收集一个真实的数据集&#xff0c;该数据集包括了房屋的销售价格、面积和房龄。 在机器学习中&#xff0c;这个数…...

K8S初级入门系列之八-网络

一、前言 本章节我们将了解K8S的相关网络概念&#xff0c;包括K8S的网络通讯原理&#xff0c;以及Service以及相关的概念&#xff0c;包括Endpoint&#xff0c;EndpointSlice&#xff0c;Headless service&#xff0c;Ingress等。 二、网络通讯原理和实现 同一K8S集群&…...

分段@Transactional 坑及失效问题

Transactional 背景&#xff1a;在某些情况下&#xff0c;我们需要分段transaction&#xff0c;在最外面没有transaction&#xff0c;里面分成几个transaction&#xff0c;保证分段是成功的。 问题代码&#xff1a; Service public Order getOrder1(String id) {Optional<Or…...

25、matlab里面的10中优化方法介绍——Opt_Golden法(matlab程序)

1.简述 基本思想 黄金分割法也称为 0.618 法&#xff0c;其基本思想是通过取试探点和进行函数值比较&#xff0c;使包含极小点的搜索区间不断缩短以逼近极小值点。适用于确定区间上的任何单谷函数求极小值的问题。 公式推导 设有定义在[ a , b ] [a,b][a,b]上的单谷函数 φ ( …...

点云拟合球体

前言&#xff1a;在很多情况下&#xff0c;需要根据点云来拟合球体&#xff0c;本博文主要介绍各种方法的拟合情况及优缺点&#xff0c;希望对各位小伙伴有所帮助&#xff01; 目录 1. vtkFitImplicitFunction进行球拟合 2. 四点求解球 1. vtkFitImplicitFunction进行球拟合 …...

基于动态规划(DP)算法的增程式EV能量管理策略研究(MATLAB编程)

文章目录 算法代码仿真结果结果分析算法代码 clc; clear; close all; load CWTVC.mat N=length(T_z); %N=200;load minFuelConsup.txt minFuel_Pe=minFuelConsup(:...

前端知识点视频补充

使用工具&#xff1a; Vscode使用&#xff1a; 需要下载插件&#xff1a;open in browser。这个插件可以快速打开浏览器。 选择文件夹有两种方式&#xff1a;选择打开文件、拖拽方式&#xff08;这种最方便&#xff09; 快捷键&#xff1a;快速生成Htm结构文件&#xff1a;…...

python多线程—终止子线程

总体思路 1、获取需要终止的子线程id 2、根据子线程id&#xff0c;终止子线程。 过程 获取子线程id&#xff1a; import threading Thread_id threading.get_ident() # 获取子线程的id值线程终止函数 def async_raise(Thread_id, exctype):"""raises th…...

#P1012. [NOIP2015提高组] 神奇的幻方

题目描述 幻方是一种很神奇的 N \times NNN 矩阵&#xff1a;它由数字 1,2,3, \ldots ,N \times N1,2,3,…,NN 构成&#xff0c;且每行、每列及两条对角线上的数字之和都相同。 当 NN 为奇数时&#xff0c;我们可以通过以下方法构建一个幻方&#xff1a; 首先将 11 写在第一行…...

(学习笔记-IP)Ping的工作原理

Ping是基于ICMP协议工作的&#xff0c;ICMP报文封装在IP包里面&#xff0c;它工作在网络层&#xff0c;是IP协议的助手。 ICMP包头的类型字段&#xff0c;大致可分为两大类&#xff1a; 一类是用于诊断的查询消息&#xff0c;也就是查询报文类型一类是通知出错原因的错误消息&…...

php 进程间通信:管道、uds

1、管道 1.1、管道概念 管道是单向的、先进先出的&#xff0c;它把进程的输出和另一个进程的输入连接在一起。一个进程往管道写入数据&#xff0c;另一个进程从管道读取数据。数据被从管道中读取出来之后&#xff0c;将被删除&#xff0c;其他进程无法在读取到相应的数据。管…...

Stable Diffusion如何生成高质量的图-prompt写法介绍

文章目录 Stable Diffusion使用尝试下效果prompt的编写技巧prompt 和 negative promptPrompt格式Prompt规则细节优化Guidance Scale 总结 Stable Diffusion Stable Diffusion是一个开源的图像生成AI系统,由Anthropic公司开发。它基于 Transformer模型架构,可以通过文字描述生成…...

MySQL 高级SQL语句(一)

目录 一、高级SQL语句&#xff08;进阶查询&#xff09; 1.1 select 1.2 distinct 1.3 where 1.4 and 和 or 1.5 in 1.6 between 1.7 通配符 1.8 like 1.9 order by 一、高级SQL语句&#xff08;进阶查询&#xff09; 先准备2个表 一个location表&#xff1a; use m…...

SkyWalking链路追踪-技术文档首页

SkyWalking 文档中文版&#xff08;社区提供&#xff09; (skyapm.github.io)https://skyapm.github.io/document-cn-translation-of-skywalking/ SkyWalking-基本概念 SkyWalking链路追踪是一个用于分布式系统的性能监控工具&#xff0c;它帮助开发人员了解系统中各组件之间…...

AndroidStudio Memory profiler(内存分析器)

1.Record Java/Kotlin allocations 查看java 层中对象的调用栈和短时间内创建对象的次数。可用于内存抖动快速分析,可用快速查找到该对象的调用栈(等同于mat) 从上图可见&#xff0c;短时间内创建了23个char[] 数组&#xff0c;其中最大的char[] 占用20k, 查看cll stack 调用…...

【C++模板进阶】

目录 一、模板使用时的一个小注意点二、非类型模板参数三、类模板的特化3.1函数模板的特化3.2类模板的特化3.2.1全特化3.2.2偏特化 四、模板的分离编译4.1模板不支持分离编译4.2模板分离编译报错的分析4.2解决方案 五、模板的总结 一、模板使用时的一个小注意点 在使用模板时&…...

(一)RabbitMQ概念-优势、劣势、应用场景 、AMQP、工作原理

Lison <dreamlison163.com>, v1.0.0, 2023.06.22 RabbitMQ概念-优势、劣势、应用场景 、AMQP、工作原理 文章目录 RabbitMQ概念-优势、劣势、应用场景 、AMQP、工作原理RabbitMQ概念RabbitMQ的优势RabbitMQ劣势RabbitMQ应用的场景RabbitMQ_AMQPRabbitMQ工作原理 RabbitM…...

JetBrains全家桶:如何自定义实现类TODO注释?

文章目录 效果图具体方法参考文献 效果图 TODO注释大家应该都用过&#xff0c;在注释开头打上TODO的话&#xff0c;软件下方的TODO选项卡里就可以自动筛选出你打了TODO的注释&#xff0c;你可以点击里面对应的注释来实现快速跳转。 jetbrains全家桶&#xff08;如Pycharm、Int…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...