https://leetcode.com/problems/decode-ways

[輸入]

length(s) = n;

[暴力法]

將s按照一位或兩位的方式切割，試過所有組何，看是否是合法並累計之。

在每個決策點 展成一顆 二元樹，故知道葉節點共有O(2^n)個；

所以暴力法複雜度是O(n*2^n)

二元樹例子如下:

[遞迴公式]:

[bottom up]

[Time Complexity]

[Space Complexity]

[Example]

[Solution]

class Solution {
public:
    int numDecodings(string s) {
        if (!s.length()) {
            return 0;
        } else if (s.at(0) == '0') {
            return 0;
        }
        vector<int> v(s.length() + 1, 0);
        v[0] = 1;
        v[1] = 1;
        int prev = s.at(0) - '0';
        for (int i = 1; i < s.length(); i++) {
            int now = (s.at(i) - '0');
            int n = 10 * prev + now;
            if (n > 26) {
                if (now == 0) {
                    return 0;
                }
                v[i + 1] = v[i];
            } else {
                if (n == 0)  {
                    return 0;
                } else if (now == 0) {
                    v[i + 1] = v[i - 1];
                } else if (prev == 0) {
                    v[i + 1] = v[i];
                } else { 
                    v[i + 1] = v[i] + v[i - 1];
                }
            }
            prev = now;
        }
        return v[s.length()];
    }
};