[数据结构与算法]leetcode 91. 解码方法（dp）

下定决心，好好过一天~

题目传送

思路：
状态要找对，不然情况会很复杂
俩种状态：
1.一个数字独立成字母时。 当是s【i】!= ‘0’ 时，dp【i】 = dp【i-1】，否则该情况对答案无贡献
2. 俩个数字成字母时。当s【i-1】和s【i】的和小于等于26，且s【i-1】不等于0时。dp【i】 += dp【i-2】

AC代码

class Solution {
public:
    int numDecodings(string s) {
    int len = s.size();
    s = " " + s;
    int dp[10005] = {0};
    dp[0] = 1;
    for(int i = 1;i <= len;i++)
    {
        if(s[i] != '0')
            dp[i] += dp[i-1];
        if(i-1 > 0 && s[i-1] != '0' && ((s[i-1]-'0')*10 + (s[i]-'0')) <= 26)
            dp[i] += dp[i-2];
    }
    return dp[len];
    }
};