【二】【动态规划NEW】91. 解码方法,62. 不同路径,63. 不同路径 II

2024-06-16 06:04

本文主要是介绍【二】【动态规划NEW】91. 解码方法,62. 不同路径,63. 不同路径 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

91. 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 :

‘A’ -> “1”
‘B’ -> “2”

‘Z’ -> “26”
要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,“11106” 可以映射为:

“AAJF” ,将消息分组为 (1 1 10 6)
“KJF” ,将消息分组为 (11 10 6)
注意,消息不能分组为 (1 11 06) ,因为 “06” 不能映射为 “F” ,这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1:

输入:s = “12”
输出:2
解释:它可以解码为 “AB”(1 2)或者 “L”(12)。
示例 2:

输入:s = “226”
输出:3
解释:它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。
示例 3:

输入:s = “06”
输出:0
解释:“06” 无法映射到 “F” ,因为存在前导零(“6” 和 “06” 并不等价)。

提示:

1 <= s.length <= 100
s 只包含数字,并且可能包含前导零。

利用递归思想写动态规划,字符串s返回解码的方法数,f(i)表示0~i区间的解码方法数.
字符串s的长度是n,我们需要得到f(n).
f(i)函数求解0~i区间的解码方法数,
可以让i位置字符单独解码,也可以让i和i-1位置字符两个一起解码.

如果让i位置字符单独解码,此时产生的解码方法数是f(i-1).
如果让i和i-1位置共同解码,此时产生的解码方法数是f(i-2).

如果让i位置字符单独解码需要满足的条件是s[i]!=‘0’.
如果让i和i-1位置字符共同解码需要满足的条件是s[i-1]!=‘0’,并且i-1和i位置字符属于1~26.

根据递归思想直接写动态规划写法.
状态表示,定义dp[i]表示0~i区间的解码方法数.
状态转移方程,如果让i位置字符单独解码,此时产生的解码方法数是dp[i-1].
如果让i和i-1位置共同解码,此时产生的解码方法数是dp[i-2].
填表顺序,填写i位置状态需要用到i-1,i-2位置状态,i需要从小到大.
初始化,特判,最开始的可以直接得出答案的就手动填写,越界的用三目表达式解决.

#define debug // 定义 debug 宏
#ifdef debug // 如果定义了 debug
#define bug(code) do{cout<<"L"<<__LINE__<<":"<<endl;code;}while(0) // 定义 bug 宏,输出当前行号并执行代码块
#else
#define bug(code) do{}while(0) // 如果没有定义 debug,bug 宏为空操作
#endifclass Solution {
public:int ret; // 用于存储结果的整数string s; // 输入字符串vector<int>dp; // 动态规划数组void solve(){ // 解决问题的函数ret=0; // 初始化结果为 0dp.assign(s.size(),-1); // 将动态规划数组初始化为 -1,大小为输入字符串的长度dp[0]=1; // 初始条件,dp[0] 设为 1for(int i=1;i<dp.size();i++){ // 从第 1 个字符开始遍历字符串int ans=0; // 用于存储当前字符的解码方法数if(s[i]!='0') ans+=dp[i-1]; // 如果当前字符不是 '0',则可以单独解码,加上 dp[i-1]if(s[i-1]!='0'&&(s[i-1]-'0')*10+(s[i]-'0')<=26) ans+=(i-2>=0?dp[i-2]:1); // 如果前一个字符不是 '0',且当前和前一个字符组成的数字小于等于 26,则可以合并解码,加上 dp[i-2](如果 i-2 小于 0,则加 1)dp[i]=ans; // 更新 dp[i] 为当前的解码方法数}ret=dp[dp.size()-1]; // 最后的结果是 dp 数组的最后一个值bug( // 如果定义了 debug,输出 dp 数组for(int i=0;i<dp.size();i++){ // 遍历 dp 数组cout<<dp[i]<<" "; // 输出 dp 数组的每一个值}cout<<endl; // 换行);}int numDecodings(string _s) { // 主函数,接收输入字符串ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); // 加速输入输出s=_s; // 将输入字符串赋值给成员变量 sif(s[0]=='0') return 0; // 如果字符串以 '0' 开头,返回 0solve(); // 调用 solve 函数求解return ret; // 返回结果}
};

62. 不同路径

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

f(i,j)表示从(0,0)位置到达(i,j)位置的路径数,我们需要的返回值是f(row,col).
f(i,j)=f(i-1,j)+f(i,j-1).
递归出口,如果是(0,0)位置,返回1.
如果越界了返回0.

利用递归思想直接写动态规划,定义状态标识dp[i][j]表示(0,0)位置到达(i,j)位置的路径数,需要的返回值是dp[row][col].
状态转移方程,dp[i][j]=dp[i-1][j]+dp[i][j-1].
初始化,特判,越界情况用三目表达式解决.
填表顺序,i需要从小到大填写.

#define debug // 定义 debug 宏
#ifdef debug // 如果定义了 debug
#define bug(code) do{cout<<"L"<<__LINE__<<":"<<endl;code;}while(0) // 定义 bug 宏,输出当前行号并执行代码块
#else
#define bug(code) do{}while(0) // 如果没有定义 debug,bug 宏为空操作
#endif  
class Solution {
public:int row, col; // 定义行数和列数int ret; // 用于存储结果的整数vector<vector<int>> dp; // 动态规划数组void solve() { // 解决问题的函数ret = 0; // 初始化结果为 0dp.assign(row + 1, vector<int>(col + 1, -1)); // 初始化 dp 数组为 -1,大小为 (row+1) x (col+1)for (int i = 1; i <= row; i++) { // 遍历每一行for (int j = 1; j <= col; j++) { // 遍历每一列if (i == 1 && j == 1) { // 如果是起点位置 (1, 1)dp[i][j] = 1; // 起点位置的路径数为 1continue; // 跳过后续计算}dp[i][j] = (i - 1 >= 1 ? dp[i - 1][j] : 0) + (j - 1 >= 1 ? dp[i][j - 1] : 0); // 计算当前位置的路径数}}ret = dp[row][col]; // 最后的结果是 dp 数组的右下角值bug( // 如果定义了 debug,输出 dp 数组for (int i = 1; i <= row; i++) { // 遍历 dp 数组的每一行for (int j = 1; j <= col; j++) { // 遍历 dp 数组的每一列cout << dp[i][j] << " "; // 输出 dp 数组的每一个值}cout << endl; // 换行}cout << endl; // 换行);}int uniquePaths(int _m, int _n) { // 主函数,接收输入的行数和列数ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速输入输出col = _n, row = _m; // 将输入的行数和列数赋值给成员变量solve(); // 调用 solve 函数求解return ret; // 返回结果}
};

63. 不同路径 II

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

提示:

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

网格里面有障碍物,填表的时候,障碍物的位置是不需要填写的,并且为了不影响其他位置的填写,如果是障碍物dp值设置为0即可,如果不设置为0,在状态转移方程哪里就需要多判断一下.
用三目运算符解决越界的情况.

#define debug // 定义 debug 宏
#ifdef debug // 如果定义了 debug
#define bug(code) do{cout<<"L"<<__LINE__<<":"<<endl;code;}while(0) // 定义 bug 宏,输出当前行号并执行代码块
#else
#define bug(code) do{}while(0) // 如果没有定义 debug,bug 宏为空操作
#endif
class Solution {
public:vector<vector<int>> arr; // 存储输入的障碍物网格int ret; // 用于存储结果的整数vector<vector<int>> dp; // 动态规划数组void solve() { // 解决问题的函数dp.assign(arr.size(), vector<int>(arr[0].size(), -1)); // 初始化 dp 数组为 -1,大小与输入网格相同for (int i = 0; i < arr.size(); i++) { // 遍历每一行for (int j = 0; j < arr[0].size(); j++) { // 遍历每一列if (arr[i][j] == 1) dp[i][j] = 0; // 如果当前位置是障碍物,路径数为 0if (arr[i][j] == 1) continue; // 如果当前位置是障碍物,跳过后续计算if (i == 0 && j == 0) { dp[i][j] = 1; continue; } // 起点位置的路径数为 1dp[i][j] = (i - 1 >= 0 ? dp[i - 1][j] : 0) + (j - 1 >= 0 ? dp[i][j - 1] : 0); // 计算当前位置的路径数}}ret = dp[arr.size() - 1][arr[0].size() - 1]; // 最后的结果是 dp 数组的右下角值}int uniquePathsWithObstacles(vector<vector<int>>& _obstacleGrid) { // 主函数,接收输入的障碍物网格ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速输入输出arr = _obstacleGrid; // 将输入的障碍物网格赋值给成员变量solve(); // 调用 solve 函数求解return ret; // 返回结果}
};

结尾

最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。
同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。
谢谢您的支持,期待与您在下一篇文章中再次相遇!

这篇关于【二】【动态规划NEW】91. 解码方法,62. 不同路径,63. 不同路径 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1065643

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

2. c#从不同cs的文件调用函数

1.文件目录如下: 2. Program.cs文件的主函数如下 using System;using System.Collections.Generic;using System.Linq;using System.Threading.Tasks;using System.Windows.Forms;namespace datasAnalysis{internal static

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

webm怎么转换成mp4?这几种方法超多人在用!

webm怎么转换成mp4?WebM作为一种新兴的视频编码格式,近年来逐渐进入大众视野,其背后承载着诸多优势,但同时也伴随着不容忽视的局限性,首要挑战在于其兼容性边界,尽管WebM已广泛适应于众多网站与软件平台,但在特定应用环境或老旧设备上,其兼容难题依旧凸显,为用户体验带来不便,再者,WebM格式的非普适性也体现在编辑流程上,由于它并非行业内的通用标准,编辑过程中可能会遭遇格式不兼容的障碍,导致操

uva 10061 How many zero's and how many digits ?(不同进制阶乘末尾几个0)+poj 1401

题意是求在base进制下的 n!的结果有几位数,末尾有几个0。 想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零,以及之前有做过的一道n阶乘的位数。 当时都是在10进制下的。 10进制下的做法是: 1. n阶位数:直接 lg(n!)就是得数的位数。 2. n阶末尾0的个数:由于2 * 5 将会在得数中以0的形式存在,所以计算2或者计算5,由于因子中出现5必然出现2,所以直接一

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验