题⽬描述
有⼀种将字⺟编码成数字的⽅式：'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，第⼀次拆解就有两种情况，然后分别对后⾯的部分分别译码，使⽤递归即可：
public class Solution46 {
public int solve (String nums) {
return recursion(nums.toCharArray(), 0);
}
public int recursion(char[] nums, int start){
if(start == nums.length){
return 1;
}
if(nums[start] == '0')
return 0;
// 使⽤⼀位字符译码
int count1 = recursion(nums,start+1);
int count2 = 0;
// 符合两位字符的译码
if((start < nums.length-1) && (nums[start] == '1' || (nums[start] == '2' &&nums[start+1] <= '6'))){
count2 = recursion(nums,start+2);
}
return count1 + count2;
}
}但是上⾯的代码时间复杂度太⾼了，只要字符稍微⻓⼀点，运⾏时间就容易超过限制了：
动态规划
我们将过程逆推，要想求得当前的字符串的译码类型，其实有两种，最后⼀个单独翻译，另外⼀种是倒数最后两个字符合起来翻译，这两者之和就是我们所要求的结果。
⽽要求前⾯的值，需要求更前⾯的值，最后⼀定会求得⼀个字符和两个字符的结果。其实这就是动态规划⾥⾯说的状态变化。递归其实就是逆推，这样会导致很多重复的计算。动态规划,则是从⼩数值计算到⼤数值。
既然我们知道是动态规划，定义 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]
- 如果nums[i]=0，说明需要和前⾯⼀个字符⼀起翻译
public class Solution {
/**
* 解码
* @param nums string字符串 数字串
* @return int整型
*/
public int solve(String nums) {
int len = nums.length();
if (len == 0 || nums.charAt(0) == '0') return 0;
int[] dp = new int[len];
dp[0] = 1;
for (int i = 1; i < len; i++) {
if (nums.charAt(i) == '0') {
if (nums.charAt(i - 1) == '1' || nums.charAt(i - 1) == '2') {
if (i == 1) {
dp[i] = 1;
} else {
dp[i] = dp[i - 2];
}
}
} else if (nums.charAt(i - 1) == '1' || (nums.charAt(i - 1) == '2' && nums.charAt(i) >= '1' && nums.charAt(i) <= '6')) {
if (i == 1) {
dp[i] = 2;
} else {
dp[i] = dp[i - 1] + dp[i - 2];
}
} else {
dp[i] = dp[i - 1];
}
}
return dp[len - 1];
}
}- 时间复杂度: 遍历计算所有的数组， O(n)
- 空间复杂度：使⽤额外的数组保存计算结果，因此空间复杂度为 O(n)