本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

一、题目描述

解码方法

一条包含字母 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 位 的整数。

二、思路分析

• 此题考查的是动态规划的问题。所谓动态规划就是将大问题简化为小问题从而攻破小问题解决大问题。
• 其实动态规划的解题思路是固定的，解题的思路总结下就是一句话：由大到小转移，从小开始解决

转移方程

• 所谓转移方程就是由大到小转移。既然想通过大问题转化到小问题那么肯定得有一个过渡的依据才行
• 一个动态规划是否可以完成主要取决在转移方程的设置上。如果理不清转移方程那么就无法实现动态规划。
• 首先我们已1121这个数字进行解码为例。因为本题编码最大值是z–>26 。 26是两位数所以1121最终加入的编码最多是两位数

• 所以1121解码有多少种可能取决于112和11两个编码 。 如果令Fx表示第x位是存在的解码数的话我们可以得出如下公式