LeetCode 91. Decode Ways

题目

动态规划

class Solution {
public:
    int dp[100005];
    int numDecodings(string s) {

        string str="";

        if(s[0]=='0')
            return 0;
        dp[0]=1;

        if(s.length()<=1)
            return dp[s.length()-1];


        str+=s[0];
        str+=s[1];

        int x = atoi(str.c_str());
        if(x<=26&&x>=1)
        {
            dp[1]++;
        }

        if(s[1]!='0')
        {

            dp[1]++;
        }

        for(int i=2;i<s.length();i++)
        {
            str="";
            str+=s[i-1];
            str+=s[i];

            int x = atoi(str.c_str());
            if(x<=26&&x>=1&&s[i-1]!='0')
            {
                dp[i] += dp[i-2];
            }

            if(s[i]!='0')
                dp[i] += dp[i-1];
        }


        return dp[s.length()-1];

    }
};