其实老早就想吐槽为什么字符串的题过半都会和动态规划扯上关系○|￣|_
一、题目：
91. 解码方法
一条包含字母
A-Z的消息通过以下映射进行了 编码 ：
2
3
4
'B' -> 2
...
'Z' -> 26要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，
"11106"可以映射为：
"AAJF"，将消息分组为(1 1 10 6)"KJF"，将消息分组为(11 10 6)注意，消息不能分组为
(1 11 06)，因为"06"不能映射为"F"，这是由于"6"和"06"在映射中并不等价。给你一个只含数字的 非空 字符串
s，请计算并返回 解码 方法的 总数 。题目数据保证答案肯定是一个 32 位 的整数。
示例 1：
2
3
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。示例 2：
2
3
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。示例 3：
2
3
4
5
输出：0
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。示例 4：
2
3
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。提示：
1 <= s.length <= 100s只包含数字，并且可能包含前导零。
不能说是完全看懂吧，只能说是根本不会
二、思路整理：
在看到题目之后，由于字符串和方案数量求解的存在，第一反应就是动态规划，毕竟字符串和数组契合度比较好，也很容易加入一个动态规划数组（想起被字符串支配的恐惧）。
通过观察可以发现‘A’到‘Z’分别映射了1~26的数字，最大的26只不过是一个两位数，所以只会出现两种解读方式——单位或双位。
那么该如何建立状态转移方程呢？我们另设一个数组用来存放当前位置对应的不同解读数量，那么在字符串中向后遍历的过程可以看作是在末尾插入新元素，此时新元素对应的动态分配数组中该填入什么呢？
上图中我们不难看出，新插入的‘4’于之前的‘1’构成了两种不同的情况——要么‘4’解释为D的映射，要么‘14’解释为N的映射。不管哪种映射，加上它对应的前字符串（图中红框和橙框部分）后可能解释的数量都等于截止对应前字符串最后一个字符（图中红点和橙点部分）时的可能解释数量。——即有ans【i】=ans【i-1】+ans【i-2】。
但是对于一些特殊情况，这个方程是错误的——比如我们现在再在‘4’后方插入一个‘5’，它将无法用‘45’进行解释（超过了26这个边界）方程变成了ans【i】=ans【i-1】，而如果插入的是‘0’，运气恐怕就不会那么好了——整个字符串将不会再存在任何合理解释——即直接返回0。
好嘛……确定状态转移方程5分钟，处理边界条件2小时。
不过历史告诉我们一个道理——路越走越硌脚了，十有八九你走错道了，边界判断你越处理越难受，也说明多半方法出问题了。
还记得我们之前在最长公共子序列中提到过的防止边界判定的方法吗——将第一个元素置零，这个问题中同样奏效，只不过设置后要注意字符串与动态规划数组有一位的偏差。
三、代码：
1 | int numDecodings(char * s){ |
四、涩图：
（直接点过来的面壁思过去(╬▔皿▔)凸）
每天的题解可以不写，但是涩图一定要放出来ψ(｀∇´)ψ！！！
