# 91 - Decode Ways

解法一 - Dynamic programming

我們可以把 dp[i] 定義成從第 0 位到第 i-1 個 letter 之間有幾種 decode 方式。

所以就可以寫出，舉例來說，假設我們在看 "126" 的 "6" 這一位：

1. 因為 6 本身就能是一個字母，所以這可以跟 dp[i-1] 的 decode 方式銜接(也就是不管 dp[i-1] 是什麼樣的字母組合，都可以加上 "F" 這一個字母)，也就有 dp[i-1] 種方式。

2. 因為 26 也可以是一個字母，所以這可以跟 dp[i-2] 的 decode 方式銜接(也就是不管 dp[i-2] 是什麼樣的字母組合，都可以加上 "Z" 這一個字母)，也就有 dp[i-2] 種方式。

另外因為我們會需要往回看到 i-2，所以我們需要定義 dp[0]，為了讓 dp[2] 是 valid，所以把 dp[0] 定義成 1。

class Solution {
public:
    int numDecodings(string s) {
        int n = s.length();  
        vector<int> dp(n+1,0);
        dp[0] = 1;
        dp[1] = s[0] == '0' ? 0 : 1; // We might have "0" as input

        for(int i=2; i<=n; i++) {
            int unit = (s[i-1] - '0');
            int tens = stoi(s.substr(i-2, 2));

            // If current digit is from 1-9, 
            // we have at least dp[i-1] decode ways
            if(unit <= 9 && unit >= 1)
                dp[i] += dp[i-1]; 

            // If previous and current digit forms 10-26, 
            // we have at least dp[i-2] decode ways
            if(tens <= 26 && tens >= 10) 
                dp[i] += dp[i-2];
        }

        return dp[n];
    }
};