导航

题面解析AC代码

题面

原题链接 一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1 'B' -> 2 ... 'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。 题目数据保证答案肯定是一个 32 位的整数。

解析

使用动态规划算法求解，定义$f[i]$表示由前$i$个字符可以解码回去的字符串集合，考虑1位解码和两位解码的情况，转移方程为 $$\begin{gathered} f[i]=f[i]+f[i-1] \\ f[i]=f[i]+f[i-2]\text{if}(s[i-1]{-}^{\prime }{0}^{\prime })\ast 10+(s[i]{-}^{\prime }{0}^{\prime })\in [10,26] \end{gathered}$$

AC代码

class Solution { public: int numDecodings(string s) { int n=s.size(); s = ' '+s; vector<int> f(n+1); f[0]=1; for(int i=1; i<=n; ++i){ if(s[i]>='1' && s[i]<='9') f[i]+=f[i-1]; if(i>1){ int t=(s[i-1]-'0')*10+s[i]-'0'; if(t>=10 && t<=26) f[i]+=f[i-2]; } } return f[n]; } };