动态规划 —— 斐波那契数列模型-解码方法
1. 解码方法
题目链接:
91. 解码方法 - 力扣(LeetCode)
https://leetcode.cn/problems/decode-ways/description/


2. 题目解析
1. 对字母
A - Z进行编码1-26
2.
11106可以解码为1-1-10-6或者11-10-6, 但是11-1-06不能解码
3. 0n不能解码
4. 字符串非空,返回解码方法的总数

3. 算法原理
1. 状态表示:以i位置为结尾
dp[i]表示:以i位置为结尾时,解码方法的总数
创建dp(n+1)的dp表,第一个位置用作虚拟位置,对应的第i个位置映射的下标也为i,只用初始化第一个dp表的位置即可
2. 状态转移方程
根据最近的一步来划分问题:
1. s[i]位置单独解码
a.解码成功,1<=a<=9,dp[i-1]
b.解码失败,0
2. s[i-1] 与 s[i]进行解码
a.解码成功,10<=b*10+a<=26,dp[i-2]
b.解码失败,0
本题的状态转移方程是:dp[i] = dp[I-1] + dp[I-2](解码成功的情况下,解码失败即为0)
3. 初始化 :把dp表填满不越界,让后面的填表可以顺利进行
dp[i]表示:以i位置为结尾时,解码方法的总数
1. 以0位置为结尾,说明只有一个字符,一个字符的解码方案数要么是1,要么是0,当dp[0]为1<=a<=9时,解码成功,否则失败
2.以1位置为结尾,说明有两个字符,两个字符的解码方案数要么是1,要么是0,要么是2
4. 填表顺序
本题的填表顺序是:从左到右
5. 返回值 :题目要求 + 状态表示
本题的返回值是:直接返回dp[n-1]
4. 代码
动态规划的固定四步骤:1. 创建一个dp表
2. 在填表之前初始化
3. 填表(填表方法:状态转移方程)
4. 确定返回值
class Solution {
public:int numDecodings(string s) {int n=s.size();//创建dp表vector<int>dp(n);//在填表之前初始化dp[0]=s[0]!='0';//初始化0位置为结尾,dp[0]在1~9之间//处理边界化if(n==1) return dp[0];//如果只有一位数的话就直接返回//如果第一个位置的值和第二个位置的值都可以单独编码if(s[0]!='0' && s[1]!='0') dp[1]+=1;//如果需要进行组合解码 10<=b*10+a<=26int t=(s[0]-'0')*10+s[1]-'0';//前两个位置所表示的数if(t>=10 && t<=26) dp[1]+=1;//0~9之间解码会出现01,02之类的// 填表for(int i=2;i<n;i++){//如果单独编码if(s[i]<='9'&&s[i]>='1') dp[i]+=dp[i-1];//如果和前面的一个数联合起来编码int t=(s[i-1]-'0')*10+s[i]-'0';if(t>=10&&t<=26) dp[i]+=dp[i-2];}return dp[n-1];}
};完结撒花~
相关文章:
 
动态规划 —— 斐波那契数列模型-解码方法
1. 解码方法 题目链接: 91. 解码方法 - 力扣(LeetCode)https://leetcode.cn/problems/decode-ways/description/ 2. 题目解析 1. 对字母A - Z进行编码1-26 2. 11106可以解码为1-1-10-6或者11-10-6, 但是11-1-06不能解码 3. 0n不能解码 4. …...
 
PPT / Powerpoint中利用LaTeX输入公式
PPT / Powerpoint中利用LaTeX输入公式_ppt插入latex公式-CSDN博客文章浏览阅读2.8w次,点赞42次,收藏75次。新版的Word(Office 2016后?)是支持LaTeX公式输入的,但是Powerpoint并不支持。下面介绍如何利用。_…...
C++ 模板专题 - 类型擦除
一:概述 C 中的类型擦除(Type Erasure)是一种技术,允许你在不暴露具体类型信息的情况下,通过统一的接口处理不同的类型。这种技术常用于实现泛型编程,特别是在需要支持多种不同类型的情况下,如容…...
 
RuoYi-Vue项目 重点代码讲解
1. RuoYi-Vue项目 常规说明: ruoyi-admin:后台接口开发(主要存放控制层相关代码)ruoyi-common:通用工具ruoyi-framework:框架核心ruoyi-generator:代码生成(可以移除)r…...
pandas习题 024:用字典构造 DataFrame
编码题)用 Python 的字典构造一个 DataFrame,它有 a、b 两列,三行数据。其中 a 列值为 1、4、7,b 列值为 2、5、8,索引为 x、y、z。 即: ‘’’ a b x 1 2 y 4 5 z 7 8 ‘’’ import pandas as pddf = pd.DataFrame({a: [1, 4,...
 
如何在Node.js中执行解压缩文件操作
一、解压文件 1.安装依赖: 安装adm-zip依赖包:npm install adm-zip --save 安装iconv-lite依赖包:npm install iconv-lite --save 解压前的file文件夹结构: update-1.0.2.zip压缩包内容: 2.在depresssFile.js文件&…...
 
梦熊 CSP-S模拟赛 T3 youyou 的序列 II
原题链接 题目大意 给定一个长度为 n 的非负整数序列 a ,初始时所有数字均被标记为蓝色,youyou 和 yy 轮流对序列 a 进行操作,由 youyou 开始。 • 如果当前是 youyou 的回合,那么他可以至多选择连续的 c 1 个数…...
记录下docker部署gitlab-ce-17.5版本及客户端git拉取方式配置
服务端部署 # 提前拉取镜像 docker pull gitlab/gitlab-ce:17.5.0-ce.0docker run -d \ --name gitlab \ --hostname gitlab.test.cn \ -p 443:443 \ -p 88:80 \ -p 2222:22 \ --restartalways \ -v /data/gitlab/config:/etc/gitlab \ -v /data/gitlab/logs:/var/log/gitlab …...
opencv-platform实现人脸识别
和同事接触了下甲方,对方算是一个资源整合的自由人,手里有项目,然后认识些开发就聊下有什么事情可以做的,对方聊了下做人脸签到,或者说人脸打开。就这方面我做了下简单的了解。做了个java小demo。 我们常用的人脸识别的摄像头屏幕…...
 
leetcode 有重复字符串的排列组合
1.题目要求: 2.题目代码: class Solution { public://运用回溯vector<string> result;string s;void backtricking(string S,vector<bool>& used){if(s.size() S.size()){result.push_back(s);return;}for(int i 0;i < S.size();i){if(i >…...
 
【大数据学习 | kafka】kafka的组件架构
broker:每个kafka的机器节点都会运行一个进程,这个进程叫做broker,负责管理自身的topic和partition,以及数据的存储和处理,因为kafka是集群形式的,所以一个集群中会存在多个broker,但是kafka的整体又不是一…...
 
Python基于TensorFlow实现简单循环神经网络回归模型(SimpleRNN回归算法)项目实战
说明:这是一个机器学习实战项目(附带数据代码文档视频讲解),如需数据代码文档视频讲解可以直接到文章最后关注获取。 1.项目背景 Simple RNN是一种基础的循环神经网络,它能够处理序列数据,例如文本、时间序…...
torch.isclose
torch.isclose是 PyTorch 中的一个函数,用于判断两个张量中的对应元素是否接近相等。 其函数签名为:torch.isclose(input, other, rtol1e-05, atol1e-08, equal_nanFalse)。 参数说明: input 和 other:要进行比较的两个张量。r…...
 
Python记录-字典
定义 Python 中的字典(dictionary)是一种内置的数据结构,用于存储键值对(key-value pairs)。字典中的每个键(key)都是唯一的,并且与一个值(value)相关联。键…...
 
python读取学术论文PDF文件内容
目录 1、PyPDF22、pdfplumber3、PyMuPDF4、pdfminer总结 1、PyPDF2 PyPDF2 是一个常用的库,可以用来读取、合并、分割和修改PDF文件。读取pdf内容: import PyPDF2# 打开PDF文件 with open(ELLK-Net_An_Efficient_Lightweight_Large_Kernel_Network_for…...
5550 取数(max)
经验值:2000 时间限制:1000毫秒 内存限制:128MB 庐阳区2020年信息学竞赛试题 不许抄袭,一旦发现,直接清空经验! 题目描述 Description 盒子里面有N个球,每个球上都一个数。你每次可以取走一…...
 
Windows常用网络命令
ipconfig 功能:查看维护本地的IP地址 ipconfig 显示计算机中网络适配器的ip地址、子网掩码及默认网关。 ipconfig /all 显示所有网络适配器(网卡、拨号连接等)的完整tcp/ip配置信息。与不带参数的用法相比,它的信息更全更多&am…...
地磁传感器(学习笔记上)
在咱们地磁传感器里的开发板: 开发板上的地磁传感器型号是QMC5883L,它也是使用I2C与ESP32通信,I2C地址为0X0D。这个项目,我们使用地磁传感器QMC5883L计算方位角,最终,把开发板放平到桌子上,旋转…...
 
使用 NumPy 和 Matplotlib 进行高级数据可视化:实践指南
使用 NumPy 和 Matplotlib 进行高级数据可视化:实践指南 数据科学和工程实践中,NumPy 和 Matplotlib 是强大的组合工具。本文将进一步展示如何借助这两个库进行更复杂的可视化任务,例如创建多曲线、叠加图、动态可视化等场景。 一、环境准备…...
mysql 启动报错 ‘/var/run/mysqld/mysqld.sock‘
问题描述: Docker 拉取 Ubuntu镜像,启动ubuntu容器后 在里边安装mysql 当容器启动时,不将/var/lib/mysql 目录映射到宿主机时,mysql可以正常启动使用当容器启动时,将/var/lib/mysql 目录映射到宿主机后,my…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
 
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
 
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
 
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
 
day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
 
Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
 
若依登录用户名和密码加密
/*** 获取公钥:前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...
规则与人性的天平——由高考迟到事件引发的思考
当那位身着校服的考生在考场关闭1分钟后狂奔而至,他涨红的脸上写满绝望。铁门内秒针划过的弧度,成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定",构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...


