这个动态规划有点难,因为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;
    }
};