题⽬描述
有⼀种将字⺟编码成数字的⽅式：‘a’->1, ‘b->2’, … , ‘z->26’。
现在给⼀串数字，返回有多少种可能的译码结果
示例1 输⼊：“12” 返回值：2 说明：2种可能的译码结果（”ab” 或”l”）
示例2 输⼊：“31717126241541717” 返回值：192 说明：192种可能的译码结果
仔细观察，就会发现上⾯的编码从 1 到 26，也就是可能⼀次译码使⽤是 1 位，也可能是⼀次译码⽤了 2位，⽐如 12，可以第⼀次⽤ 1，2 分开分别译码，也可以把 1，2 合并起来进⾏译码。
思路及解法
暴力递归
假设⼀个字符是S，第⼀次拆解就有两种情况，然后分别对后⾯的部分分别译码，使⽤递归即可：
但是上⾯的代码时间复杂度太⾼了，只要字符稍微⻓⼀点，运⾏时间就容易超过限制了：
记忆化递归
为了避免重复计算子问题，我们使用一个备忘录（memo）来存储已经计算过的结果。
时间复杂度：O(n)，每个子问题最多被计算一次。
空间复杂度：O(n)，递归栈的深度和备忘录的空间
动态规划
将过程逆推，要想求得当前的字符串的译码类型，其实有两种，最后⼀个单独翻译，另外⼀种是倒数最后两个字符合起来翻译，这两者之和就是我们所要求的结果。
⽽要求前⾯的值，需要求更前⾯的值，最后⼀定会求得⼀个字符和两个字符的结果。其实这就是动态规划⾥⾯说的状态变化。递归其实就是逆推，这样会导致很多重复的计算。动态规划,则是从⼩数值计算到⼤数值。
既然我们知道是动态规划，定义 dp[i] 为数字串从左到右第i个数字结尾的当前数字串所拥有的翻译⽅法数，接着就需要找出状态转移⽅程：
如果 i=0 , dp[i]=1
否则
如果nums[i]=0，说明需要和前⾯⼀个字符⼀起翻译
如果i == 1，以10或者20开头， dp[i] = 1
否则，数字串中存在10或者20的情况下，当前译码数等于后退两步的译码数， dp[i] =dp[i-2];
否则，在符合字符范围内， dp[i]=dp[i-1]+dp[i-2]
时间复杂度：O(n)，需要遍历整个字符串一次。
空间复杂度：O(n)，用于存储
dp数组。
空间优化动态规划（推荐）
观察上面的代码可以发现，计算 dp[i]时只依赖于 dp[i-1]和 dp[i-2]。因此，我们可以不用维护整个数组，只用两个变量来滚动记录之前的状态即可，从而将空间复杂度优化到常数级别。
时间复杂度：O(n)。
空间复杂度：O(1)，只使用了固定数量的变量