https://leetcode-cn.com/probl...递归解法没有functools.lru_cache会超时importfunctoolsclass解法：@functools.lru_cache()defnumDecodings(self,s:str)->int:iflen(s)==0ors[0]=='0':return0iflen(s)==1:return1iflen(s)==2:x=2if(s[0]=='1'ors[0]=='2'ands[1]<'7')else1ifs[1]=='0':x-=1returnxx=self.numDecodings(s[1:])如果s[0]=='1'或s[0]=='2'且s[1]<'7':x+=self.numDecodings(s[2:])returnxcannotdecodedifsstartsfrom0,returns0(ifsnotstartswith0)slengthis1returns1withlength2,有四种情况：都可以作为两个一位数（既不是0），也不是两位数，例如“12”。只能用作两个数字，例如'32'。只能作为两位数使用，只有'10'和'20'两种情况。无法解析，例如“30”。那么如果长度大于2，可以尝试将字符串分为：首位和后两位以及后两位（前两位组成的数字需要在1-26范围内）动态编程类解决方案：defnumDecodings(self,s:str)->int:l=len(s)ifl==0ors[0]=='0':return0ifl==1:return1dp=[0]*ldp[0]=1dp[1]=2如果s[0]=='1'或s[0]=='2'并且s[1]<'7'否则1s[1]=='0':dp[1]-=1print(dp)foriinrange(2,l):ifs[i]!='0':dp[i]+=dp[i-1]如果s[i-1]=='1'或s[i-1]=='2'且s[i]<'7':dp[i]+=dp[i-2]returndp[-1]dp[i]有两种情况：如果前一位不为??0，则可以累加前一位的值；如果前一个的值加上当前值大于0小于27，则可以累加前一个的前一个值。欢迎来到我的博客：https://codeplot.top/我的博客分类：https://codeplot.top/categories/%E5%88%B7%E9%A2%98/
