题目：
难度：Middle
相关话题：字符串、动态规划
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空 字符串，请计算解码方法的总数。
示例 1:
输入: "12"
输出: 2
解释:它可以解码为 "AB"（1 2）或者 "L"（12）。
示例2:
输入: "226"
输出: 3
解释:它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
思路：
DP，dp[i+1]为当前索引i以及之前的字符串有多少种组合，
那么，如果存在一个i(i>0)，那么dp[i+1]=s[i]的组合*dp[i] + (s[i-1],s[i])的组合*dp[i-1]。
例如：[1,3,6,2,1,2]:
当i为2，对应的s[i]为6，那么dp[i+1]就是(6的组合 * [1,3]的组合) + ([3,6]的组合 * [1]的组合)。
如果索引i为1，那么前面只有1位数，因此我们初始默认dp[0]=1。
最后就是组合的算法，1位数的组合计算就是除了输入为"0"返回0，其他都可以返回1。
2位数的组合计算，需要判断这个2位数是否在[10,26]之内，在则返回1，不在的返回0； 如果一个2位数是07，也是同样返回0，这里不能当做1位数来计算，否则会重复。
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* @param {string} s
* @return {number}
*/
var numDecodings = function(s) {
let dp=[]
dp[0]=1
dp[1]=s[0]==="0" ? 0 : 1
for(let i=1;i<s.length;i++){
dp[i+1]=calc1(s[i])*dp[i]+calc2(s[i-1],s[i])*dp[i-1]
}
return dp[dp.length-1]
function calc1(s){
if(s==="0")return 0
else return 1
}
function calc2(s1,s2){
let n=+(s1+s2)
if(n<=26 && n>=10){
return 1
}else{
return 0
}
}
};
扩展阅读：