class Solution {
public:
    int solve(string nums) {
        if(nums[0]=='0') return 0;
        int n=nums.size();
        vector<int> dp(n+1,1);
        for(int i=2;i<=n;i++){
            if(nums[i-1]=='0'){
                if(nums[i-2]>'2') return 0;//0的前面不是1、2时为非法串
                dp[i]=dp[i-2];//与前面的1、2绑定
            }
            else if(nums[i-2]=='1' || (nums[i-2]=='2' && nums[i-1]<='6'))
                dp[i]=dp[i-1]+dp[i-2];
            else
                dp[i]=dp[i-1];
        }
        return dp[n];
    }
};
在dp数组中只用到了连续2个值,空间优化:
class Solution {
public:
    int solve(string nums) {
        if(nums[0]=='0') return 0;
        int n=nums.size();
        int d1=1,d2=1,d3=1;
        for(int i=2;i<=n;i++){
            if(nums[i-1]=='0'){
                if(nums[i-2]>'2') return 0;//0的前面不是1、2时为非法串
                d3=d1;//与前面的1、2绑定
            }
            else if(nums[i-2]=='1' || (nums[i-2]=='2' && nums[i-1]<='6'))
                d3=d1+d2;
            else
                d3=d2;
            d1=d2;d2=d3;
        }
        return d3;
    }
};
时间复杂度O(n),空间复杂度O(1)