算法日常・每日刷题--＜动态规划＞4-北京尧图网络

91. 解码方法 - 力扣LeetCode91. 解码方法 - 一条包含字母 A-Z 的消息通过以下映射进行了编码 1 - A2 - B...25 - Y26 - Z然而在解码已编码的消息时你意识到有许多不同的方式来解码因为有些编码被包含在其它编码当中2 和 5 与 25。例如11106 可以映射为 * AAJF 将消息分组为 (1, 1, 10, 6) * KJF 将消息分组为 (11, 10, 6) * 消息不能分组为 (1, 11, 06) 因为 06 不是一个合法编码只有 6 是合法的。注意可能存在无法解码的字符串。给你一个只含数字的非空字符串 s 请计算并返回解码方法的总数。如果没有合法的方式解码整个字符串返回 0。题目数据保证答案肯定是一个 32 位的整数。示例 1输入s 12输出2解释它可以解码为 AB1 2或者 L12。示例 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 只包含数字并且可能包含前导零。https://leetcode.cn/problems/decode-ways/题目描述一条包含字母A-Z的消息通过以下映射进行编码A - 1 B - 2 ... Z - 26给定一个只包含数字的字符串s请计算一共有多少种解码方式。注意0无法单独映射成任何字母06不能当成6解码必须是10~26的两位数才合法。示例输入s 12输出21 2AB、12L输入s 226输出32 2 6、22 6、2 26输入s 06输出0开头 0 无法解码动态规划五步1. dp 数组定义dp[i]字符串前 i 个字符s[0] ~ s[i-1]拥有的解码方案总数。数组长度为n1dp[0]代表空字符串dp[n]就是整个字符串的答案。2. 状态转移逻辑我们处理前i个字符有两种合法解码分支单独解码最后一位如果s[i-1] ! 0这一位可以单独作为一个编码方案数继承dp[i-1]。两位合并解码取最后两位组成数字如果数值在10 ~ 26之间可以把这两位看成一个整体方案数继承dp[i-2]。3. dp 数组初始化dp[0] 1空串设置为 1是 DP 递推的基准。不是说空串有真实解码是为了两位合并计算时方便。dp[1]对应字符串第 1 个字符s[0]。如果s[0] 0直接无法解码dp[1]0否则dp[1]1。4. 遍历顺序dp[i]依赖dp[i-1]和dp[i-2]所以从左向右遍历i 从 2 循环到 n。5. 返回结果dp[n]前 n 个字符完整字符串的解码方案总数。#include vector #include string using namespace std; class Solution { public: int numDecodings(string s) { int n s.size(); vectorint dp(n 1); dp[0] 1; dp[1] (s[0] 0) ? 0 : 1; for(int i 2; i n; i) { dp[i] 0; // 当前位可以单独解码 if(s[i-1] ! 0){ dp[i] dp[i-1]; } // 判断最后两位是否10~26 int val (s[i-2] - 0) * 10 (s[i-1] - 0); if(val 10 val 26){ dp[i] dp[i-2]; } } return dp[n]; } };

算法日常・每日刷题--＜动态规划＞4

相关推荐

多元AI芯片跑PyTorch不再难：Torch-FL虚拟设备机制与算子适配实战

claude code（九）：【Claude Code官方最佳实践7️⃣】:用 headless mode 无头模式把 output-format 改到 TaoToken

OpenShell：跨平台终端体验重构方案，统一Linux/macOS/WSL开发环境

更多资讯

当下值得推荐的SEO优化企业，究竟有哪些？

河北内贸网站关键词优化哪家专业

绵阳大面积纹身好店复盘，画家纹身凭啥稳居第一？

从 POS 到 CRM：服装门店会员数据为什么不能只放在收银里

工业级MRAM存储方案：GD32VF103VBT6驱动MR25H40CDF实战

（142页PPT）PLM+ERP系统选型及建设方案建议书（附下载方式）

今日更新

插件加载失败深度解析：从did not activate到生命周期排查指南

SpringBoot+Vue+MyBatis企业级房屋租赁管理系统源码解析

企业核心数据灾备自动化：用 OpenClaw 备份到本地 + 云端 + 离线存储的 TaoToken 统一通道实践

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？