Chapter 5: Recursion and Dynamic Programming

知识解析

5.1 问题空间

5.2 加法原理和乘法原理

我们最早在小学数学中接触过加法原理和乘法原理，他们的内容是：

加法原理：如果做一件事情有n类方法，每类方法都可以完整完成这件事情，那么做这件事情的总方法数量，就是把每一类方法的数量加和起来。比如从A到C市，有5种公交，3种地铁，2种计程车，那就有 $5 + 3 + 2$种方法。

乘法原理：如果做一件事情有n个步骤，每个步骤都不可或缺，那么做这件事情的总方法数量，就是把每个步骤的方法数量乘起来。比如从A到C市需要经过B市，A到B市有3种方法，B到C市有5种方法，那么就有 $3 * 5$ 种方法。

无论你有没有意识到，这两个原理会经常在递归和动态规划中用到。因为求解一个问题空间（1维/2维/3维）内“有多少个”的问题，就是在求从起点到终点有多少条路径的问题，那么对每个方向就应该用加法原理，对于同一方向路径的每一步骤，就应该用乘法原理。

e.g. A message containing letters from A-Z is being encoded to numbers, using 'A' -> 1, 'B' -> 2, ... 'Z' -> 26 . Given a non-empty string containing only digits, determine the total number of ways to decode it. (LeetCode: Decode Ways)

decode这件事有两种方法，第一种是先decode第一个数字再decode剩下的，第二种是先decode第二个数字再decode剩下的，两种方法之间用加法原理。这两种方法都有两个步骤，所以步骤之间要用乘法原理。两种方法的第一个步骤，视数字的范围有0或者1种decode方法。

所以有递推关系 $decode(n) = x * decode(n-1) + y * decode(n-2), x, y = 0 or 1$

由递推关系可以看到与fibonacci数列求解的相似性（只不过每次可能有0-2个分支，而不总是2个分支）。不难想到同样的，可以用三个变量，用 $O(n)$时间和 $O(1)$ 空间内解决。

Base Case 永远要写在最前面，尤其是检查memoization cache的前面。

[TODO] 看的方向总是与走的方向相反，因为我们只能查过去走的数据。从左往右走，那就看左边的。从右往左走，就看右边的。 e.g. two sum