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)