P88. 解码方式

https://algocasts.io/episodes/n5Gqb4pA

哥,还是不太懂d(0)为什么等于1,能举个例子吗?

@Yifu_Chen

比如给你的加密字符串是 “12”,已经知道动态规划解法中,状态 d(i) 表示字符串 s 中前 i 个字符的解码方式数量。 那么 “12” 的解码方式数量就是 d(2),表示前 2 个字符的解码方式数量:

  • 我们先看 “12” 中的 2,可以解码成 B,于是把 2 解码成 B 这条路径下有 d(1) 种方式;
  • 然后看 “12” 中的 12,可以解码成 L,于是把 12 解码成 L 这条路径下有 d(0) 种方式。

我们只关注第二点,d(i) 最终变成 d(0) 时,说明了一件事情,我们从右向左把字符串做了一次有效解码(这个例子中是把 12 解码成 L),因此边界条件的 d(0) 只能等于 1。

以上的例子,最终解答就是:

d(2) = d(1) + d(0) = 1 (解码成 AB) + 1 (解码成 L) = 2

在动态规划求解的问题中,边界条件 d(0) = 1,或者 d(0, 0) = 1 是非常常见的。你不能用状态定义去解读它,比如这道题目,你用状态定义解读 d(0) 就是字符串 s 中前 0 个字符的解码方式数量。你会觉得,这根本就没有含义,应该等于 0。然而事实并非如此,d(0) 或 d(0, 0) 这时往往代表的是完成了一次有效组合完成了一次有效分解完成了一组有效操作 等等。因此它应该等于 1,而不是 0。