[每日一题]DP二：最优子结构

接着昨天的总结写： [每日一题]DP小结一：重叠子问题

DP 算法的优点在于解决了朴素递归算法的重复计算问题。昨天我们总结了自底向上 和 自顶向下的 两种DP写法。一般的情况下，这两种写法都是等价的，除了一种特殊情况：自底向上的规模比较大，但是自顶向下的规模比较容易缩小的情况下，不适合使用自底向上的算法。

举个例子：397. Integer Replacement 。

给定任意的一个正整数 n ， 当 n 是偶数的时候，n 可以替换成 2 ； 当 n 是奇数的时候，n 可以替换成 n + 1 或者 n - 1。 求 最少经过多少次替换可以使得 n  等于 1 。

这道题有很多解法，我们在这篇总结里只讨论 DP 的解法。

本题可以抽象成一颗树，树的根节点是 n , 叶子节点的值都是 1，在每一个节点的决策路径是 ： 当 n 是偶数的时候， n = n / 2; 当 n 是奇数的是 n = n + 1 或者 n = n - 1。

根据定义，我们可以推出如下的等式

1. 如果 n 是偶数: f(n) = f(n/2) + 1

2. 如果 n 是奇数： f(n) = min(f(n-1), f(n+1)) + 1
   
   

以 n  = 9 为例，那么 n 经过一系列的替换 变成 1 的可能方案有如下几种：

1. 5个步骤：9 -> 8 -> 4 -> 2 -> 1

2. 5个步骤：9 -> 10 -> 5 -> 4 -> 2 -> 1

3. 7个步骤：9 -> 10 -> 5 -> 6 -> 3 -> 4 -> 2 -> 1

4. 9个步骤：9 -> 10 -> 5 -> 6 -> 3 -> 5 -> 6 -> 3 -> 2 -> 1

5. ...

我们发现 f(5)、f(4) 都有重复计算，所以我们可以用 DP 来求解。如果我们用 自顶向下的方案求解的话，n 的规模可以迅速缩小，比如 n = 10000 ， 只需要执行一步， n = 5000 就可以缩小一半的规模。但是如果用 自底向上的方案，我们需要求出 1 到 10000 的所有子问题的最优解，很显然复杂度太高了。

最优子结构的定义是：问题的最优解是由相关子问题的最优解组合而成，而这些子问题都是可以独立求解的。也就是说一个问题的最优解包含其子问题的最优解。

最优子结构不好理解，我们先来看个反例。