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.
題意：如果從A到Z可以按1-26進(jìn)行編碼其爵，那么給出一串?dāng)?shù)字瘫想，有多少種解碼方式？
思路：
例如給出1221，如果從頭開始用深度搜索的方式找，對于每一位，都有可能有兩種解碼方法，時間復(fù)雜度將會非常高。
換一種角度榨馁，對于以每一位結(jié)尾的字符串來說，它的解碼方法和前面數(shù)字串解碼的方式相關(guān)帜矾，有點像jump那道題翼虫，可以用動態(tài)規(guī)劃的方法解決屑柔。
以dp[n]表示從頭到第n-1位有多少種解碼方法，如果當(dāng)前位置n的數(shù)字是1-9珍剑，那么dp[n] += dp[n-1]掸宛，如果n-1位不等于0并且和n位組合起來的數(shù)字小于等于26，dp[n] += dp[n-2]招拙。dp[0]需要初始化為1唧瘾，因為計算dp[2]時，如果前兩位組合是一個合法的編碼别凤，將需要dp[0]饰序。
public int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int len = s.length();
int[] dp = new int[len + 1];
dp[0] = 1;
dp[1] = s.charAt(0) != '0' ? 1 : 0;
for (int i = 2; i <= len; i++) {
if (s.charAt(i-1) != '0') {
dp[i] += dp[i-1];
}
if (s.charAt(i-2) != '0' && Integer.valueOf(s.substring(i-2, i)) <= 26) {
dp[i] += dp[i-2];
}
}
return dp[len];
}