LeetCode: Decode Ways

Title:

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.

思路：题目都没有懂，谈什么思路。一定要先读懂题。。。

动态规划，每次看一个，如果这个元素f(n)是有效的（除了0都有效），有效，就是 f(n) = f(n-1)再看下前一位和这一位的组合是不是有效，有效再加上f(n-2)，f(n) += f(n-2)

class Solution{
public:
    int numDecodings(string s) {
        int n = s.size();
        if (0 == n)
            return 0;
        int * dp = new int [n+1];
        for (int i = 0 ; i < n+1; i++)
            dp[i] = 0;
        dp[0] = 1;//这里为什么是1？因为后面的推导公式是f(n) = f(n-1) + f(n-2)
        if (isValid(s.substr(0,1)))
            dp[1] = 1;
        else
            dp[1] = 0;
        for (int i = 1; i < n; i++){
            if (isValid(s.substr(i,1))){
                dp[i+1] = dp[i];
            }
            if (isValid(s.substr(i-1,2))){//判断是否能和前面一个组成有效
                dp[i+1] += dp[i-1];//将后面这两个看做是一个整体
            }
        }
        return dp[n];
    }    
    bool isValid(string s){
        if (s[0] == '0')
            return false;
        if (s.size() == 1)
            return true;
        if (s.size() == 2){
            if (s[0] > '2')
                return false;
            else{
                if (s[0] == '2' && s[1] > '6')
                    return false;
                else
                    return true;
            }
        }
        return false;

    }
};