题目
解码方法
非常明显，递归可以做，可能会爆栈，最佳方法是DP。
求状态转移方程。
首先考虑最后一个数字的解码方式。以f[i]表示前 i个字符串的解码方式总数。如果选择一个数字，此时的解码方式数就是:fi=fi-1, 当然 s[i-1]不能是字符0。
如果选择两个字符进行解码， 此时解码方式数是：fi=fi-2。此时i >= 2, s[i-2]不能是字符0，而且s[i-2]和s[i-1]组成的数字介于1～26。
所以最终的解码方式数应该是这两部分的相加。
dp[0]应该是什么呢？"" 有几种解码方式？ 1=> 仍然是空字符串
程序基本框架就是：
dp size -> s.length + 1
dp[0] = 1
i from 1 to dp.size
if s[i-1] != '0'
dp[i] += dp[i-1]
if i>=2 and s[i-2] != '0' and (10*s[i-2]+s[i-1]) <= 26
dp[i] += dp[i-2]
ans = dp[i]
数组版本代码
class Solution {
public int numDecodings(String s) {
int length = s.length();
int[] dp = new int[length+1];
dp[0] = 1;
for(int i = 1;i <= length;i++){
if(s.charAt(i-1) != '0'){
dp[i] += dp[i-1];
}
if(i >= 2 && s.charAt(i-2) != '0' && (10*(s.charAt(i-2)-'0')+s.charAt(i-1)-'0') <= 26 && (10*(s.charAt(i-2)-'0')+s.charAt(i-1)-'0' > 0)){
dp[i] += dp[i-1];
}
}
return dp[length];
}
}
时间复杂度：O（n+1-1）=> O(n)
空间复杂度：O（n+1）=> O(n)
向后计算时，dp数组前面的元素已经被丢弃了，实际使用的只有最近的两个元素。和斐波纳切数列很像。
class Solution {
public int numDecodings(String s) {
int length = s.length();
int fn_1 = 1;
int fn_2 = 0;
int fn = 0;
for(int i = 1;i <= length;i++){
fn = 0;
if(s.charAt(i-1) != '0'){
fn += fn_1;
}
if(i >= 2 && s.charAt(i-2) != '0' && (10*(s.charAt(i-2)-'0')+s.charAt(i-1)-'0') <= 26 && (10*(s.charAt(i-2)-'0')+s.charAt(i-1)-'0' > 0)){
fn += fn_2;
}
fn_2 = fn_1;
fn_1 = fn;
}
return fn;
}
}
时间复杂度： O(n)
空间复杂度： O(1)
