LeetCode题目：Decode Ways，一维动态规划

从后往前动态规划，要注意临界状态，可以用占位符来避免程序内的越界判断。


Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).
The number of ways decoding “12” is 2.


暴力递归，大集合超时

class Solution {
public:
    int numDecodings(string s) {
        if(s.size() == 0)
            return 0;
        if(s.size() == 1 && s[0] != '0')
            return 1;
        if(s[0] == '0')
            return 0;
        int fix = s.size() == 2 ? 1: 0;
        if(s[0] == '1' || (s[0] == '2' && s[1] <= '6'))
            return numDecodings(s.substr(1)) + numDecodings(s.substr(2)) + fix;
        return numDecodings(s.substr(1));
    }
};

动态规划，16ms过大集合

class Solution {
public:
    int numDecodings(string s) {
        if(s.size() == 0)
            return 0;
        vector ways(s.size() + 2,1);//多出来的两个作为占位符，避免程序内判断是否超过size
        for(int i = s.size() - 1; i >= 0; --i)
        {
            //self
            if(s[i] == '0')
                ways[i] = 0;
            else
                ways[i] = ways[i+1];
            
            //self and next
            if( i + 1 < s.size() && ((s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6')))) {
                ways[i] += ways[i + 2];
            }
        }
        return ways[0];
    }
};

Code rewrite at 2013-1-4, not very nice

class Solution {
public:
    int numDecodings(string s) {
        if (s.size() == 0) return 0;
        if (s[0] == '0') return 0;
        int *ways = new int[s.size()];
        ways[0] = 1;
        for(int ei = 1; ei < s.size(); ++ei) {
            char last = s[ei - 1];
            char cur = s[ei];
            if(cur == '0') {
                if(last == '1' || last == '2')
                    ways[ei] = ei > 1 ? ways[ei-2] : 1;
                else {
                    delete ways;
                    return 0;
                }
            } else if(last == '1' || (last == '2' && cur <= '6')) {
                ways[ei] = ways[ei-1];
                ways[ei] += ei > 1 ? ways[ei-2] : 1;
            } else {
                ways[ei] = ways[ei-1];
            }
        }
        int ret = ways[s.size() - 1];
        delete ways;
        return ret;
    }
};