[leetcode Decode Ways] 掌握动态规划

原题：

给定一串数字，求出有多少种编码方式。看完这道题目，第一反应想到的是使用DFS。一个字母最多编码成一个两位数，因此每次遍历的时候要么取一个数字，要么两个数字，每次遍历的时候判断数字是否合法，若能遍历到最后一个数字则编码成功。比如说，我以"101"为例：第一次取"1"，然后判断"1"有没有对应的字母，若存在，则截掉第一个数字，剩下"01"，继续进行递归，否则直接返回；或者判断"10"有没有对应的字母，若存在，则截掉前面两个数字，剩下"1"，继续进行递归，否则直接返回。若最后只剩下一个空字符串，则解码成功。大致就是对一棵二叉树进行遍历一遍。这样的解法在少量数据的情况下还能用。代码大概是这样，在leetcode提交后，毫无悬念得提示超时。

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty()) {
            return 0;
        }
        int result = 0;
        dfs(s, &result);
        return result;
    }
    
private:
    bool isValidLetter(string str) {
        if (str[0] == '0') {
            return false;
        }
        int num;
        if (str.size() == 1) {
            num = str[0] - '0';
        } else {
            num = (str[0] - '0') * 10 + (str[1] - '0');
        }
        return num >= 1 && num <= 26;
    }
    
    void dfs(string str, int *result) {
        
        if (str.size() >= 1) {
            if (isValidLetter(str.substr(0, 1))) {
                dfs(str.substr(1), result);
            } else {
                return;
            }
        }
        
        if (str.size() >= 2) {
            if (isValidLetter(str.substr(0, 2))) {
                dfs(str.substr(2), result);
            } else {
                return;
            }
        }
        
        if (str.size() == 0) {
            (*result)++;
        }
    }
};

这道题可以用动态规划来做，dp[i]表示前i个(包括i)数字有多少种解码方式。当i=0时，dp[0] = 0; i = 1呢，dp[1]就等于1吗？未必，可能第一个数字为0，那就无法解码出对应的字母，因此还需要视情况而定。当i=n呢，第n个数字可能单独作为一个字母，也可能与它前一个数字组合成一个字母。因此，我们初步得到状态转移方程：

(1) dp[0] = 0

(2) dp[1] = 1, if str[1] is valid
    dp[1] = 0, if str[1] is not valid

(3) dp[n] = dp[n - 1] + dp[n - 2]

第三个方程咋看起来好像没有问题，但是第n个数字就一定能保证可以解码成一个合法的字母？同样，第n个数字与它前一个数字的组合就一定保证解码成一个合法的字母？在上述状态转义方程中，我们没有对它进行判断。经过分析后，第三个方程看起来应该是这样的：

dp[n] = 0
if str[n] is valid
    dp[n] += dp[n - 1]
if str[n - 1] combine str[n] is valid
    dp[n] += dp[n - 2]

看起来完美了，但上面的代码还有个小问题。当n = 2时，若第2个字母与第一个字母的组合合法，则dp[2] += dp[0]，但是dp[0]我们一开始已经给它赋值为0。因此当n = 2时，即使合法，也相当于没有进行累加。所以，这里要稍加判断，修改后的代码如下：

dp[n] = 0
if str[n] is valid
    dp[n] += dp[n - 1]
if str[n - 1] combine str[n] is valid
    dp[n] += (i - 2 == 0) ? 1 : dp[n - 2]

正确得写出状态转义方程后，实现代码应该不难：

class Solution {
public:
    int numDecodings(string s) {
        int dp[s.size() + 1];
        //将数组初始化为0
        memset(dp, 0, sizeof(int) * (s.size() + 1));
        
        //判断第一个数字是否合法，若不合法，直接返回0
        if (s.size() >= 1) {
            if (isValid(s[0])) {
                dp[1] = 1;
            } else {
                return 0;
            }
        }
        
        for (int i = 1; i < s.size(); i++) {
            if (isValid(s[i])) {
                dp[i + 1] += dp[i];
            }
            
            if (isValid(s[i - 1], s[i])) {
                dp[i + 1] += ((i-1)==0?1:dp[i - 1]);
            }
        }
        return dp[s.size()];
    }
    
private:
    bool isValid(char c1, char c2) {
        if (c1 == '0') {
            return false;
        }
        int num = (c1 - '0') * 10 + (c2 - '0');
        return num >= 1 && num <= 26;
        
    }
    
    bool isValid(char c) {
        int num = c - '0';
        return num >= 1 && num <= 26;
    }
};