leetcode91. 解码方法

分析

解码时s[i]要么与前面的字母s[i-1]一起解码，要么就分开自己成为新解码，用f[i]表示第i个字母有多少种解法，那么转移转移方程f[i]=f[i-1]+f[i-2]，同时要保证一起解码时要<=26。

class Solution {
public:
    int numDecodings(string s) {
        int n=s.length();
        vector<int>f(n+1);
        f[0]=1;//空字符串只有一种解法
        for(int i=1;i<=n;i++){
            if(s[i-1]!='0')f[i]+=f[i-1];//选择s[i-1]
            if(i>1&&s[i-2]!='0'&&(s[i-2]-'0')*10+(s[i-1]-'0')<=26)//不选s[i-2]
                f[i]+=f[i-2];
        }
        return f[n];
    }
};