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

动态规划 —— 斐波那契数列模型-解码方法

1. 解码方法

题目链接:

91. 解码方法 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://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. 解码方法 题目链接&#xff1a; 91. 解码方法 - 力扣&#xff08;LeetCode&#xff09;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次&#xff0c;点赞42次&#xff0c;收藏75次。新版的Word&#xff08;Office 2016后&#xff1f;&#xff09;是支持LaTeX公式输入的&#xff0c;但是Powerpoint并不支持。下面介绍如何利用。_…...

C++ 模板专题 - 类型擦除

一&#xff1a;概述 C 中的类型擦除&#xff08;Type Erasure&#xff09;是一种技术&#xff0c;允许你在不暴露具体类型信息的情况下&#xff0c;通过统一的接口处理不同的类型。这种技术常用于实现泛型编程&#xff0c;特别是在需要支持多种不同类型的情况下&#xff0c;如容…...

RuoYi-Vue项目 重点代码讲解

1. RuoYi-Vue项目 常规说明&#xff1a; ruoyi-admin&#xff1a;后台接口开发&#xff08;主要存放控制层相关代码&#xff09;ruoyi-common&#xff1a;通用工具ruoyi-framework&#xff1a;框架核心ruoyi-generator&#xff1a;代码生成&#xff08;可以移除&#xff09;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.安装依赖&#xff1a; 安装adm-zip依赖包&#xff1a;npm install adm-zip --save 安装iconv-lite依赖包&#xff1a;npm install iconv-lite --save 解压前的file文件夹结构&#xff1a; update-1.0.2.zip压缩包内容&#xff1a; 2.在depresssFile.js文件&…...

梦熊 CSP-S模拟赛 T3 youyou 的序列 II

原题链接 题目大意 给定一个长度为 n 的非负整数序列 a &#xff0c;初始时所有数字均被标记为蓝色&#xff0c;youyou 和 yy 轮流对序列 a 进行操作&#xff0c;由 youyou 开始。 • 如果当前是 youyou 的回合&#xff0c;那么他可以至多选择连续的 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实现人脸识别

和同事接触了下甲方,对方算是一个资源整合的自由人&#xff0c;手里有项目&#xff0c;然后认识些开发就聊下有什么事情可以做的&#xff0c;对方聊了下做人脸签到&#xff0c;或者说人脸打开。就这方面我做了下简单的了解。做了个java小demo。 我们常用的人脸识别的摄像头屏幕…...

leetcode 有重复字符串的排列组合

1.题目要求: 2.题目代码&#xff1a; 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的机器节点都会运行一个进程&#xff0c;这个进程叫做broker&#xff0c;负责管理自身的topic和partition&#xff0c;以及数据的存储和处理&#xff0c;因为kafka是集群形式的&#xff0c;所以一个集群中会存在多个broker&#xff0c;但是kafka的整体又不是一…...

Python基于TensorFlow实现简单循环神经网络回归模型(SimpleRNN回归算法)项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档视频讲解&#xff09;&#xff0c;如需数据代码文档视频讲解可以直接到文章最后关注获取。 1.项目背景 Simple RNN是一种基础的循环神经网络&#xff0c;它能够处理序列数据&#xff0c;例如文本、时间序…...

torch.isclose

torch.isclose是 PyTorch 中的一个函数&#xff0c;用于判断两个张量中的对应元素是否接近相等。 其函数签名为&#xff1a;torch.isclose(input, other, rtol1e-05, atol1e-08, equal_nanFalse)。 参数说明&#xff1a; input 和 other&#xff1a;要进行比较的两个张量。r…...

Python记录-字典

定义 Python 中的字典&#xff08;dictionary&#xff09;是一种内置的数据结构&#xff0c;用于存储键值对&#xff08;key-value pairs&#xff09;。字典中的每个键&#xff08;key&#xff09;都是唯一的&#xff0c;并且与一个值&#xff08;value&#xff09;相关联。键…...

python读取学术论文PDF文件内容

目录 1、PyPDF22、pdfplumber3、PyMuPDF4、pdfminer总结 1、PyPDF2 PyPDF2 是一个常用的库&#xff0c;可以用来读取、合并、分割和修改PDF文件。读取pdf内容&#xff1a; import PyPDF2# 打开PDF文件 with open(ELLK-Net_An_Efficient_Lightweight_Large_Kernel_Network_for…...

5550 取数(max)

经验值&#xff1a;2000 时间限制&#xff1a;1000毫秒 内存限制&#xff1a;128MB 庐阳区2020年信息学竞赛试题 不许抄袭&#xff0c;一旦发现&#xff0c;直接清空经验&#xff01; 题目描述 Description 盒子里面有N个球&#xff0c;每个球上都一个数。你每次可以取走一…...

Windows常用网络命令

ipconfig 功能&#xff1a;查看维护本地的IP地址 ipconfig 显示计算机中网络适配器的ip地址、子网掩码及默认网关。 ipconfig /all 显示所有网络适配器&#xff08;网卡、拨号连接等&#xff09;的完整tcp/ip配置信息。与不带参数的用法相比&#xff0c;它的信息更全更多&am…...

地磁传感器(学习笔记上)

在咱们地磁传感器里的开发板&#xff1a; 开发板上的地磁传感器型号是QMC5883L&#xff0c;它也是使用I2C与ESP32通信&#xff0c;I2C地址为0X0D。这个项目&#xff0c;我们使用地磁传感器QMC5883L计算方位角&#xff0c;最终&#xff0c;把开发板放平到桌子上&#xff0c;旋转…...

使用 NumPy 和 Matplotlib 进行高级数据可视化:实践指南

使用 NumPy 和 Matplotlib 进行高级数据可视化&#xff1a;实践指南 数据科学和工程实践中&#xff0c;NumPy 和 Matplotlib 是强大的组合工具。本文将进一步展示如何借助这两个库进行更复杂的可视化任务&#xff0c;例如创建多曲线、叠加图、动态可视化等场景。 一、环境准备…...

mysql 启动报错 ‘/var/run/mysqld/mysqld.sock‘

问题描述&#xff1a; Docker 拉取 Ubuntu镜像&#xff0c;启动ubuntu容器后 在里边安装mysql 当容器启动时&#xff0c;不将/var/lib/mysql 目录映射到宿主机时&#xff0c;mysql可以正常启动使用当容器启动时&#xff0c;将/var/lib/mysql 目录映射到宿主机后&#xff0c;my…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

高防服务器价格高原因分析

高防服务器的价格较高&#xff0c;主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因&#xff1a; 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器&#xff0c;因此…...