91. Decode Ways

dp O(n) time O(n) space
跟爬楼梯那道题类似，每次只能爬一层或两层，问总共多少种爬法
最后一步：两个字符或者一个字符可以对应一个英文字母（但是要合法，两个字符要在10到26中间，一个字符不能为0）
子问题：f[i] = f[i - 1] + f[i - 2]
边界条件：f[0] = 1，即空串就只有一种decoding（这道题OJ有问题）

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty()) return 0;
        int n = s.length();
        int f[n + 1] = {1};
        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] != '0') {
                f[i] += f[i - 1];
            }
            if (i > 1) {
                auto ret = stoi(s.substr(i - 2, 2));
                if (10 <= ret && ret <= 26) {
                    f[i] += f[i - 2];
                }
            }
        }
        return f[n];
    }
};

O(n) time O(1) space

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty()) return 0;
        int n = s.length();
        int f0 = 1, f1 = 1;
        for (int i = 1; i <= n; ++i) {
            int f2 = 0;
            if (s[i - 1] != '0') {
                f2 += f1;
            }
            if (i > 1) {
                auto x = stoi(s.substr(i - 2, 2));
                if (10 <= x && x <= 26) {
                    f2 += f0;
                }
            }
            f0 = f1;
            f1 = f2;
        }
        return f1;
    }
};

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty()) return 0;
        int n = s.length();
        int f0 = 1, f1 = 1;
        for (int i = 0; i < n; ++i) {
            int f2 = 0;
            if (s[i] != '0') {
                f2 += f1;
            }
            if (i > 0) {
                auto x = stoi(s.substr(i - 1, 2));
                if (10 <= x && x <= 26) {
                    f2 += f0;
                }
            }
            f0 = f1;
            f1 = f2;
        }
        return f1;
    }
};