解码方法数

这个动态规划有点难，因为f(i)不仅与f(i-1)有关，和f(i-2)也有关系，能想明白这一层关系着实不容易0.0

设当前的解法有f(i)种，由于s[i]和s[i - 1]的搭配方式有多种，下面分情况讨论：

• 非法的情况，即不论怎么搭配都decode不了，返回0
• 合法的情况，如果只能搭配成一种，那么f(i)=f(i-1)，如果能搭配成两种，那么f(i)=f(i-1)+f(i-2)

class Solution {
public:
    /**
     *
     * @param s string字符串
     * @return int整型
     */
    int numDecodings(string s) {
        // write code here
        if(s.size() < 1 || s[0] == '0') return 0;
        int a = 1, b = 1, dp = 1;
        for (int i = 1; i < s.size(); ++i) {
            // 非法的情况
            if (s[i] == '0' && (s[i - 1] > '2' || s[i - 1] == '0')) return 0;
            // 合法的情况之可拆
            if (s[i] != '0' && ((s[i - 1] == '1') || (s[i - 1] == '2' && s[i] < '7'))) dp = a + b;
            // 合法的情况之不可拆
            else dp = b;
            a = b; b = dp;
        }
        return dp;
    }
};