题目链接：91. 解码方法

题解：

简单的动态规划题！

题目简述：

将A ~ Z编码为 1 ~ 26，给定一个数字字符串求共有多少种解码方式！

题解：

动态规划：

状态表示： f[i]表示前i个字符的解码方法数

**状态计算：**考虑最后一步

  • 最后一位不为0时，解码数为f[i - 1]
  • 最后两位为10 ~ 26时，解码数为f[i - 2]

综上所述，状态转移方程为： f[i] = f[i - 1] + f[i - 2]

最终结果： f[n]

初始转态： f[0] = 1 ，初始转态为0还是1由是否能满足所有状态的正确性决定，由于f[1] = s[1] != '0' ? 1: 0;，所以f[0] = 1!

时间复杂度：O(n)

注意：

  • 为了使得处理边界简单，将字符串前面加空格处理！

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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] != '0') f[i] += f[i - 1];
            if(i > 1){
                int t = s[i] - '0' + (s[i - 1] - '0') * 10;
                if(t >= 10 && t <= 26) f[i] += f[i - 2];
            }
        }
        return f[n];
    }
};