0%

动态规划之解码方法

一条包含字母A-Z 的消息通过以下映射进行了 编码 :

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

要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,"111" 可以将 "1" 中的每个 "1" 映射为 "A" ,从而得到 "AAA" ,或者可以将 "11""1"(分别为 "K""A" )映射为 "KA" 。注意,"06" 不能映射为 "F" ,因为 "6""06" 不同。

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

原题链接:https://leetcode-cn.com/problems/decode-ways/

动态规划解法

确定状态

最后一步

由题可知,num是一个只含数字的非空字符串,解码规则比较简单,就是1 ~ 26分别映射为A ~ Z 26个字母,我们就知道,一个数字可以解码为一个字母,两个数字也可以解码为一个字母,
所以我们在考虑最后一步时,需要考虑到这两种情况。如下图所示:

image

如上图所示,num 为 1234523,如果最后一个解码单位为3,那么另一部分为 123452;如果最后一个解码单位为23,那么另一部分为12345。

确定子问题

确定完最后一步时,我们知道了最后一步解码单位有两种,将求解num解码方式转化为求解num-1num-2两个子问题,同时问题规模相应的变小了,如果剩余的部分可继续解码,那么还可以继续进行分解,直至不可分解为止。

转移方程

由上面的确定状态可以知,我们用f(x)代表从0~x位置字符串的解码方式数,可得转移方程为:

1
f(x) = f(x-1) + f(x-2)

注意上式成立是有条件的。

初始条件和边界情况

初始条件

如果输入的字符串为空串,那么解码只有只有一种方式,也解码为空串,即f(0) = 1;

边界情况

上面提到转移方程,如果当前字符串的最后两位可以进行解码,所以最后两位必须是10~26之间的某一个数,那么前面解码才会有效,即f(x) 需要加上f(x-2);
同理如果当前字符串的最后一位可以进行解码,最后一位不能是0,那么前面解码才会有效,即f(x) 需要加上f(x-1)。

代码实现

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
30
31
public static int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 0;
}

int[] f = new int[s.length() + 1];

char[] chars = s.toCharArray();

f[0] = 1;
f[1] = chars[0] == '0' ? 0 : 1;

for (int i = 2; i <= s.length(); i++) {
// 如果要加上f[i - 2],那么i位置的前两位必须是可解码的,即在10 ~ 26 之间 像01,03这种是无效的。
String is2 = String.valueOf(chars[i - 2]) + String.valueOf(chars[i - 1]);

int i2 = Integer.parseInt(is2);
if (i2 >= 10 && i2 <= 26) {
f[i] += f[i-2];
}

// 如果要加上f[i-1],那么i位置的数字必须不能是0,否则无法继续解码
int i1 = Integer.parseInt(String.valueOf(chars[i - 1]));

if (i1 != 0) {
f[i] += f[i-1];
}
}

return f[s.length()];
}