## C++ 路径问题

news/2024/4/15 5:04:33/文章来源:https://blog.csdn.net/m0_74922218/article/details/136505971

## 例1

62. 不同路径

1.初始化

2.当前位置的条数，就是上面位置的条数 ，加上其左边位置的条数，dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

``````class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(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];}
};``````

## 例2

63. 不同路径 II

1.初始化dp

2.将obstacleGrid中为0 的值映射到dp表中为0即可

``````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));dp[0][1] = 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]; }
};``````

## 例3

LCR 166. 珠宝的最高价值

``````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));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];}
};``````

## 例4

931. 下降路径最小和

``````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));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 = 1; i <= n; i++)ret = min(ret, dp[n][i]);//没有int和long long 的比较return ret;}
};``````

## 例5

64. 最小路径和

最小：：：初始化为INT_MAX；

dp[0][1] = 0方便dp[1][1]

``````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] = 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];}
};``````

## 例6

174. 地下城游戏

求的是dp[0][0]，那么就是从左下往右上填写dp表

dp表里的值代表的是+-之后的血量，dp[m][n - 1] = dp[m - 1][n] = 1;这一步代表走到这俩位置还能保持一格血，这俩位置不会+-血，也就是 +- 完dp[m - 1][n - 1]后还剩下1滴血

dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];等价于：当前需要的血量 = 下一步较小的血量 - 需要+-的血量，如果所需是0，则改成1

``````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];}
};``````

### Material UI 5 学习01-按钮组件

Material UI 5 学习01-按钮组件 一、安装Material UI二、 组件1、Button组件1、基础按钮2、variant属性3、禁用按钮4、可跳转的按钮5、disableElevation属性6、按钮的点击事件onClick 2、Button按钮的颜色和尺寸1、Button按钮的颜色2、按钮自定义颜色3、Button按钮的尺寸 3、图…

### Golang Channel 详细原理和使用技巧

1.简介 Channel(一般简写为 chan) 管道提供了一种机制:它在两个并发执行的协程之间进行同步&#xff0c;并通过传递与该管道元素类型相符的值来进行通信,它是Golang在语言层面提供的goroutine间的通信方式.通过Channel在不同的 goroutine中交换数据&#xff0c;在goroutine之间…

### YOLOSHOW - YOLOv5 / YOLOv7 / YOLOv8 / YOLOv9 基于 Pyside6 的图形化界面

YOLOSHOW 是一个基于 PySide6&#xff08;Qt for Python&#xff09;开发的图形化界面应用程序&#xff0c;主要用于集成和可视化YOLO系列&#xff08;包括但不限于YOLOv5、YOLOv7、YOLOv8、YOLOv9&#xff09;的目标检测模型。YOLOSHOW 提供了一个用户友好的交互界面&#xff…

### 一文详解：Open SSL

Open SSL是 SSL (传输层安全)和 TLS (传输层安全)协议的健壮的开源实现。这些加密协议被广泛用于保护计算机网络上的通信&#xff0c;通过在两个通信应用程序之间提供隐私和数据完整性。从更实际的角度来说&#xff0c;OpenSSL 是一个工具包&#xff0c;其中包含各种命令行实用…

### Android使用OpenGL和FreeType绘制文字

Open GL主要是渲染图形的&#xff0c;有时候需要绘制文字&#xff0c;网上搜了一下&#xff0c;基本思路都是把文字转成位图&#xff0c;再使用Open GL纹理进行渲染。为了保证灵活性&#xff0c;我们把每个可能用到的字符都生成一个位图加载到纹理缓冲区&#xff0c;绘制字符串…

### 【Web安全】XSS攻击与绕过

【Web安全】XSS攻击与绕过 【Web安全靶场】xss-labs-master 1-20 文章目录 【Web安全】XSS攻击与绕过1. XSS攻击是啥&#xff1f;2. XSS如何发生&#xff1f;3. XSS分类3.1. 反射型3.2. 存储型3.3. DOM型 4. XSS攻击方式1. script标签2. img标签3. input标签4. details标签5.…

### MySQL 学习笔记（基础篇 Day2）

「写在前面」 本文为黑马程序员 MySQL 教程的学习笔记。本着自己学习、分享他人的态度&#xff0c;分享学习笔记&#xff0c;希望能对大家有所帮助。推荐先按顺序阅读往期内容&#xff1a; 1. MySQL 学习笔记&#xff08;基础篇 Day1&#xff09; 目录 3 函数 3.1 字符串函数 3…