My code:

public class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0)
            return 0;
        if (s.charAt(0) < '1' || s.charAt(0) > '9')
            return 0;
        else if (s.length() == 1)
            return 1;
        int[] dp = new int[s.length() + 1];
        if (s.charAt(0) >= '1' && s.charAt(0) <= '9')
            dp[1] = 1;
        else
            dp[1] = 0;
        dp[0] = 1;
        for (int i = 2; i < dp.length; i++) {
            if (s.charAt(i - 1) < '0' || s.charAt(i - 1) > '9')
                return 0;
            int v = Integer.parseInt(s.substring(i - 2, i));
            
            if (v > 9 && v <= 26)
                dp[i] += dp[i - 2];
            if (s.charAt(i - 1) > '0' && s.charAt(i - 1) <= '9')
                dp[i] += dp[i - 1];
            else if (s.charAt(i - 1) == '0' && dp[i] == 0)
                return 0;
        }
        return dp[dp.length - 1];
    }
    public static void main(String[] args) {
        Solution test = new Solution();
        System.out.println(test.numDecodings("10"));
    }
}

My test result:

Paste_Image.png

这道DP花了我接近两个小时，看了别人的代码，理解了好久才搞懂。
其实，DP的话，思路一定要清晰。比如这道题目。
求这个东西。
那么我设一个数组， dp[s.length()+1]
dp[i] 表示从s[0] - s[i - 1] 这一段区域，有多少种构造方法。
那么，有多少种呢？只有两种可能。

1. (s[i - 2], s[i - 1])
2. (s[i - 2]), (s[i - 1])
   那么就直接点，考虑第一种因素。
   即前面两位在 1-26之间就行了。
   于是，dp[i] += dp[i - 2], 先把第一种情况加上去
   这个很容易计算。
   此时，不需要去考虑什么0不0的。
   然后考虑第二种情况。
   那么，因为DP，我可以保证s[i - 2] 是符合的。
   于是只用判断s[i - 1]是否符合 1-9.
   如果是， dp[i] += dp[i - 1]
   然后还需要考虑一种情况， 如果 s[i - 1] == '0' 呢？
   按道理，是无法进行下去了，应该直接返回0.
   但是如果s[i - 2] 在 1-2范围内，就可以构成，10, 20，于是可以继续进行下去。
   那么该怎么区分这种情况呢？难道还要再去判断下s[i - 2]？
   不用了，如果s[i - 2] 在 1-2 范围内，就满足了第一种情况，那么dp[i] 就已经被赋值了，已经大于0了。
   所以最后只用判断下dp[i]是否为0，是否被赋值过了，如果没有。代表s[i - 2]不在1-2范围内。那么这里就无法再继续decode，得直接返回0.

一开始这道题目我是拿递归做的，思路和permutation那个类型差不多，但是超时了。的确其中有许多重复的地方。

DP还是难啊。
贴一个博客。
http://bangbingsyb.blogspot.com/2014/11/leetcode-decode-ways.html

DP，思路一定要清晰，最好能像这里一样清楚地写下来。

**
总结： String, DP
**

Good luck, Richardo!

My code:

public class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int n = s.length();
        int[] dp = new int[n];
        dp[0] = (isDigit(s.charAt(0)) ? 1 : 0);
        for (int i = 1; i < n; i++) {
            int sum = 0;
            char curr = s.charAt(i);
            if (isDigit(curr)) {
                if (i - 1 >= 0) {
                    sum += dp[i - 1];
                }
                else {
                    sum += 1;
                }
            }
            String sub = s.substring(i - 1, i + 1);
            if (isValid(sub)) {
                if (i - 2 >= 0) {
                    sum += dp[i - 2];
                }
                else {
                    sum += 1;
                }
            }
            dp[i] = sum;
        }
        
        return dp[n - 1];
    }
    
    private boolean isValid(String s) {
        char c1 = s.charAt(0);
        char c2 = s.charAt(1);
        if (c1 == '1' && (c2 >= '0' && c2 <= '9')) {
            return true;
        }
        else if (c1 == '2' && (c2 >= '0' && c2 <= '6')) {
            return true;
        }
        else {
            return false;
        }
    }
   
    private boolean isDigit(char curr) {
        if (curr >= '1' && curr <= '9') {
            return true;
        }
        else {
            return false;
        }
    }
}

这道题目我的思路还是很清晰的。
一开始我做的方向不对。
我又想到了用 divide and conquer, burst ballon + cache
这是一定可以work的。但存在一个问题，很难解决，或者需要很多的琐碎代码去解决。
如果输入是 '111'
那么，我的算法，会重复计算很多东西。而且很难察觉。只能通过hashset 来去重。这样的话，开销会变大。

于是我转而用 iteration DP.

dp[i] 表示， [0, i] number of decode ways
那么，
如果 s.charAt(i) 本身就是digit，dp[i] += dp[i - 1]
如果 s.substring(i - 1, i + 1) 是 "11 - 26"中的一员，那么
dp[i] += dp[i - 2]

然后加上一些corner case, 就可以完成这个问题了。
思路很直接。

Anyway, Good luck, Richardo! -- 08/26/2016