題目：
你有一個僅包含數字的字串，要求將其轉換成字母。字母的編碼規則如下：

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

請問這個字串有多少種不同的解碼方法？

範例：

輸入: s = "12"
輸出: 2
解釋: 它可以被解碼為 "AB"（1 2）或者 "L"（12）。

輸入: s = "226"
輸出: 3
解釋: 它可以被解碼為 "BZ"（2 26）, "VF"（22 6）, 或者 "BBF"（2 2 6）。

解題思路

每次可以選一個字母或兩個字母，然後可以從上一個狀態解法轉移過來，很像之前做過得 #70. Climbing Stairs 題目，

實作：

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        int n = s.size();
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = s[0] == '0' ? 0 : 1;
        for (int i = 2; i <= n; i++) {
            int oneDigit = stoi(s.substr(i-1, 1));
            if (oneDigit >= 1 && oneDigit <= 9) {
                dp[i] += dp[i-1];
            }

            int twoDigits = stoi(s.substr(i-2, 2));
            if (twoDigits >= 10 && twoDigits <= 26) {
                dp[i] += dp[i-2];
            }
        }
        return dp[n];
    }
};

參考：
#91. Decode Ways