leetcode15，LeetCode91 Decode Ways

題目：

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).

leetcode15。The number of ways decoding?"12"?is 2. （Medium）

?

分析：

開始想到的就是暴力搜索，但是超時了，所以考慮用動態規劃來做。

符合單序列動態規劃的特點，所以有

leetcode 1、1. 狀態：dp[i]表示前i個字符組成的子串可能的解碼方式。

2. 初始化：dp[0] = 1, dp[1] = 1（s[0] != '0'，因為沒有0這個對應數字）

3. 遞推關系：

一般情況下：

if s[i - 1]與s[i -2]組成的在“1” ~“26”范圍內， dp[i] = dp[i - 1] + dp[i - 2];

LeetCode、　　　　　　　　　　　　　　　　　　 else， dp[i] = dp[i - 1];

但要注意的是，如果s[i - 1] == '0'需要特殊處理，當s[i - 2] == '1' || '2'時， dp[i] = dp[i - 2]

　　　　　　　　　　　　　　　　　　　　　　 否則，則說明這個0沒有對應位，這個字符串無法解碼，直接返回0；

4.結果： dp[s.size()];

代碼：

class Solution {
public:
    int numDecodings(string s) {
        if (s.size() == 0) {
            return 0;
        }
        int dp[s.size() + 1];
        dp[0] = 1;
        if (s[0] != '0') {
            dp[1] = 1;
        }
        for (int i = 2; i <= s.size(); ++i) {
            if (s[i - 1] == '0') {
                if (s[i - 2] == '1' || s[i - 2] == '2') {
                    dp[i] = dp[i - 2];
                    continue;
                }
                else {
                    return 0;
                }
            }
            if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6') ) {
                dp[i] = dp[i - 1] + dp[i - 2];
            } 
            else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[s.size()];
    }
};

LeetCode Online Judge？?

?

?

?

2. 遞推關系：