- 1
- 2
- 3
- 4
- 5
用动态规划求解解码方法II含星号的过程.docx
资料介绍
用动态规划求解解码方法II含星号的过程
问题定义
给定一个包含数字 0-9 和星号 * 的字符串，其中 * 可以代表任意数字 1-9。按照编码规则（1 对应 A……26 对应 Z）解码，求共有多少种不同的解码方法。结果需要对一个大数取模。
例如 s = "1*"，* 可代表 1-9，能解码出的方式共 9 + 9 = 18 种（* 单独解码有 9 种，与 1 组合解码 11-19 有 9 种）。
问题分析
含星号的解码问题比普通解码复杂，因为 * 具有多种取值可能，需要分别枚举其作为"单个字符"与"与前一个字符组合"时的所有情况。
动态规划建模
设 dp[i] 表示前 
个字符的解码方法数。仍按"最后一个字符如何解码"分类：
1. 单个字符解码：若 s[i-1] 为数字 1-9，则有 1 种；若为 *，则有 9 种（代表 1-9）。
2. 两个字符组合解码：枚举 s[i-2..i-1] 组成的两位数在 10-26 之间的情况。需要分四种情形分别统计：两数字、数字+星号、星号+数字、星号+星号。
最终 dp[i] 为单字符与双字符两种情况之和。因结果可能很大，需对 取模。
部分文件列表
| 文件名 | 大小 |
| 用动态规划求解解码方法II含星号的过程.docx | 38K |
最新上传
- 打赏
- 30日榜单
-
yahuang001 打赏3.00元 3天前
-
yahuang001 打赏1.00元 3天前
-
zhongshaoxiong 打赏3.00元 3天前
-
他山之石可攻玉 打赏60.00元 3天前
用户：烟雨
-
江岚 打赏210.00元 3天前
用户：潇潇江南
-
江岚 打赏100.00元 3天前
-
21ic下载 打赏310.00元 3天前
用户：gsy幸运
-
21ic下载 打赏310.00元 3天前
用户：zhengdai
-
21ic下载 打赏310.00元 3天前
用户：江岚
-
21ic下载 打赏210.00元 3天前
用户：潇潇江南
-
21ic下载 打赏60.00元 3天前
用户：他山之石可攻玉
-
21ic下载 打赏60.00元 3天前
用户：烟雨
-
21ic下载 打赏60.00元 3天前
用户：w178191520
-
21ic下载 打赏60.00元 3天前
用户：w993263495
-
21ic下载 打赏110.00元 3天前
用户：xzxbybd
-
21ic下载 打赏60.00元 3天前
用户：zq_1943
-
21ic下载 打赏20.00元 3天前
用户：kk1957135547
-
21ic下载 打赏20.00元 3天前
用户：sun2152
-
21ic下载 打赏20.00元 3天前
用户：铁蛋锅
-
21ic下载 打赏20.00元 3天前
用户：xuzhen1
-
21ic下载 打赏20.00元 3天前
用户：w1966891335
-
21ic下载 打赏35.00元 3天前
用户：有理想666
-
21ic下载 打赏15.00元 3天前
用户：nuaanuaa111
-
21ic下载 打赏20.00元 3天前
用户：liqiang9090
-
21ic下载 打赏15.00元 3天前
用户：ningmengge
-
21ic下载 打赏10.00元 3天前
用户：mulanhk
-
21ic下载 打赏5.00元 3天前
用户：asys
-
21ic下载 打赏10.00元 3天前
用户：舞蹈荀彧
-
21ic小能手 打赏5.00元 3天前
资料：磁编码器开源方案
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
江岚 打赏20.00元 3天前
-
江岚 打赏50.00元 3天前
-
江岚 打赏20.00元 3天前
-
江岚 打赏10.00元 3天前
-
21ic小能手 打赏10.00元 3天前
-
21ic小能手 打赏8.00元 3天前
-
21ic小能手 打赏8.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏3.00元 3天前
全部评论(0)