### 题目

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26


Given an encoded message containing digits, determine the total number of ways to decode it.

For example, Given encoded message 12, it could be decoded as AB (1 2) or L (12).

The number of ways decoding 12 is 2.

### 暴力递归 $O(2^n)$

1 + "2345"子问题
12 + "345"子问题


1 + "0345"子问题  # "0345"不是正确的编码格式，会解码错误
10 + "345"子问题


#### 代码

public class Solution {
public int numDecodings(String s) {
if (s.length() == 0) { return 0; }
char[] c = s.toCharArray();
int[] count = new int[]{ 0 };
recursive(c,0,count);
return count[0];
}
public void recursive(char[] c, int cur, int[] count) {
if (cur >= c.length) { count[0]++; return; }
if (c[cur] == '0') { return; }
recursive(c,cur+1,count);
if (cur+1 < c.length && (c[cur] == '1' || (c[cur] == '2' && c[cur+1] <= '6'))) {
recursive(c,cur+2,count);
}
}
}


### 自底向上的动态规划 $O(n)$

#### 代码

public class Solution {
public int numDecodings(String s) {
if (s.length() == 0) { return 0; }
char[] c = s.toCharArray();
Map<Integer,Integer> memo = new HashMap<>();
memo.put(s.length(),1);
return recursive(c,0,memo);
}
public int recursive(char[] c, int cur, Map<Integer,Integer> memo) {
Integer res = memo.get(cur);
if (res != null) { return res; }
if (c[cur] == '0') {
memo.put(cur,0);
return 0;
}
res = recursive(c,cur+1,memo);
if (cur+1 < c.length && (c[cur] == '1' || (c[cur] == '2' && c[cur+1] <= '6'))) {
res = res + recursive(c,cur+2,memo);
}
memo.put(cur,res);
return res;
}
}


### 简单用int[]替代Map做备忘录

#### 代码

public class Solution {
public int numDecodings(String s) {
if (s.length() == 0) { return 0; }
char[] c = s.toCharArray();
int[] memo = new int[c.length+1];
Arrays.fill(memo,-1);
memo[c.length] = 1;
return dp(c,0,memo);
}
public int dp(char[] c, int cur, int[] memo) {
Integer res = memo[cur];
if (res != -1) { return res; }
if (c[cur] == '0') {
memo[cur] = 0;
return 0;
}
res = dp(c,cur+1,memo);
if (cur+1 < c.length && (c[cur] == '1' || (c[cur] == '2' && c[cur+1] <= '6'))) {
res = res + dp(c,cur+2,memo);
}
memo[cur] = res;
return res;
}
}


### 迭代版动态规划

#### 代码

public class Solution {
public int numDecodings(String s) {
if (s.length() == 0) { return 0; }
char[] c = s.toCharArray();
int[] memo = new int[c.length+1];
memo[c.length] = 1;
for (int i = c.length-1; i >= 0; i--) {
if (c[i] == '0') { memo[i] = 0; continue; }
if (i+1 < c.length && (c[i] == '1' || (c[i] == '2' && c[i+1] <= '6'))) {
memo[i] = memo[i+1] + memo[i+2];
} else {
memo[i] = memo[i+1];
}
}
return memo[0];
}
}