Here, I try to provide not only code but also the steps and thoughts of solving this problem completely which can also be applied to many other DP problems.

(1) Try to solve this problem in Backtracking way, because it is the most straight-forward method.

```
E.g '12*3'
12*3
/ \
12*(3) 12(*3)
/ \ / \
12(*)(3) 1(2*)(3) 1(2)(*3) ""
/ \ \ /
1(2)(*)(3) "" "" ""
/
""
```

(2) There are many nodes visited multiple times, like `12`

and `1`

. Most importantly, the subtree of those nodes are "exactly" the same. The backtracking solution possibly can be improved by DP. Try to merge the same nodes.

```
12*3
/ \
12* |
| \ |
| 12
| / |
1 |
\ |
""
```

(3) Successfully merge those repeated nodes and find out the **optimal substructure**, which is:

```
current state = COMBINE(next state , next next state)
e.g
12*
/ \
COMBINE (few different conditions)
/ \
12 1
```

Therefore, we can solve this problem by DP in **bottom-up** way instead of top-down **memoization**.

Now, we formulate the **optimal substructure**:

```
dp[i] = COMBINE dp[i-1] and dp[i-2]
```

where **dp[i] --> number of all possible decode ways of substring s(0 : i-1)**. Just keep it in mind.

But we need to notice there are some different conditions for this COMBINE operation.

(4) The pseudo code of solution would be:

```
Solution{
/* initial conditions */
dp[0] = ??
:
/* bottom up method */
foreach( i ){
dp[i] = COMBINE dp[i-1] and dp[i-2] ;
}
/* Return */
return dp[last];
}
```

The COMBINE part will be something like:

```
// for dp[i-1]
if(condition A)
dp[i] +=?? dp[i-1];
else if(condition B)
dp[i] +=?? dp[i-1];
:
:
// for dp[i-2]
if(condition C)
dp[i] +=?? dp[i-2];
else if(condition D)
dp[i] +=?? dp[i-2];
:
```

(5) The core step of this solution is to find out all possible conditions and their corresponding operation of combination.

```
For dp[i-1]:
/ \
/ \
s[i-1]='*' s[i-1]>0
| |
+ 9*dp[i-1] + dp[i-1]
For dp[i-2]:
/ \
/ \
s[n-2]='1'||'2' s[n-2]='*'
/ \ / \
s[n-1]='*' s[n-1]!='*' s[n-1]='*' s[n-1]!='*'
/ \ | | / \
s[n-2]='1' s[n-2]='2' num(i-2,i-1)<=26 | s[n-1]<=6 s[n-1]>6
| | | | | |
+ 9*dp[i-2] + 6*dp[i-2] + dp[i-2] + 15*dp[i-2] + 2*dp[i-2] + dp[i-2]
```

(6) Fill up the initial conditions before i = 2.

Because we need to check if num(i-2,i-1)<=26 for each i, we make the bottom-up process to begin from i=2. Just fill up the dp[0] and dp[1] by observation and by the definition of **dp[i] --> number of all possible decode ways of substring s(0 : i-1)**.

```
dp[0]=1;
/ \
s[0]=='*' s[0]!='*'
| |
dp[1]=9 dp[1]=1
```

(7) The final Solution:

```
public int numDecodings(String s) {
/* initial conditions */
long[] dp = new long[s.length()+1];
dp[0] = 1;
if(s.charAt(0) == '0'){
return 0;
}
dp[1] = (s.charAt(0) == '*') ? 9 : 1;
/* bottom up method */
for(int i = 2; i <= s.length(); i++){
char first = s.charAt(i-2);
char second = s.charAt(i-1);
// For dp[i-1]
if(second == '*'){
dp[i] += 9*dp[i-1];
}else if(second > '0'){
dp[i] += dp[i-1];
}
// For dp[i-2]
if(first == '*'){
if(second == '*'){
dp[i] += 15*dp[i-2];
}else if(second <= '6'){
dp[i] += 2*dp[i-2];
}else{
dp[i] += dp[i-2];
}
}else if(first == '1' || first == '2'){
if(second == '*'){
if(first == '1'){
dp[i] += 9*dp[i-2];
}else{ // first == '2'
dp[i] += 6*dp[i-2];
}
}else if( ((first-'0')*10 + (second-'0')) <= 26 ){
dp[i] += dp[i-2];
}
}
dp[i] %= 1000000007;
}
/* Return */
return (int)dp[s.length()];
}
```

P.S The space complexity can be further improved to O(1) because the current state i is only related to i-1 and i-2 during the bottom-up.