动态规划教做人
目录
题目
有一种将字母编码成数字的方式: ‘a’ -> 1, ‘b’ -> 2, … , ‘z’ -> 26.
现在给一串数字，给出有多少种可能的译码结果。
读题
一位数的时候, 只有一种解码; 两位数时, 如果数字在 1 到 26 之间, 就可以有两种解码. 要特别注意一下 0, 它本身是没有解码的, 只有 10 和 20 可以解码, 也就是说 100, 30 这种输入是没有解码结果的.
求解
首先是输入是否合法, 对于无输入或者 0, 直接返回 0.
之后从前向后扫描, 对于非 0 元素, 会有两种情况: 它与前面的数字在 1 到 26 之间, 或者不在. 如果不在, 那么它对于解码方法的增加没有贡献, 也是就和它前面的字符串的解码方式相等; 如果在 1 到 26 之间, 就会有把它当成1位数解码和当成2位数解码两种方式, 那么整个字符串的解码方式加 1.
如果扫描到 0, 那么不但它对解码方式增加没有贡献, 还会限制它前面的一个字符: 组合成 10 或 20 时, 0 前面的字符就不能和更前面的字符组合成两位数, 这时解码方式等于前n-2个字符的解码方式; 而如果不能组合成 10 或者 20, 就没办法进行解码, 解码方式为 0.
C++ 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int solution(string str) {
// 排除空输入或者 0 开头的数字
if (str.size() == 0 || str.front() != '0') {
return 0;
}
// dp[i] 表示到第 i 个字符为止所有解码方式
vector<int> dp(str.size(), 0);
// 上面判断了第一个字符不是 0, 所以有一种解码
dp[0] = 1;
// 从前向后遍历
for (int i = 1; i < str.size(); ++i) {
// 如果当前位不是 0, 那么至少和之前的解码数目相同
if (str[i] != '0') {
dp[i] = dp[i - 1];
}
// 如果可以和前面组合成可解码数字, 解码方式增加
if (dp[i - 1] == '1' || (dp[i - 1] == '2' && dp[i] < '6')) {
if (i - 2 < 0) {
// 正好是最前面的两个数字, 直接加 1
++dp[i];
} else {
// 否则再加上前 i - 2 位解码方式
dp[i] += dp[i - 2];
}
}
}
// dp 中最后一个元素就是到到最后一个字符为止的解码方式
return dp.back();
}
看到 dp 数组只用到了两个元素, 空间占用上可以再优化, 不过那样就更看不懂了, 不写了.