接着昨天的总结写：[每日一题]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。
根据定义，我们可以推出如下的等式
如果 n 是偶数: f(n) = f(n/2) + 1
如果 n 是奇数： f(n) = min(f(n-1), f(n+1)) + 1
以 n = 9 为例，那么 n 经过一系列的替换 变成 1 的可能方案有如下几种：
5个步骤：9 -> 8 -> 4 -> 2 -> 1
5个步骤：9 -> 10 -> 5 -> 4 -> 2 -> 1
7个步骤：9 -> 10 -> 5 -> 6 -> 3 -> 4 -> 2 -> 1
9个步骤：9 -> 10 -> 5 -> 6 -> 3 -> 5 -> 6 -> 3 -> 2 -> 1
...
我们发现 f(5)、f(4) 都有重复计算，所以我们可以用 DP 来求解。如果我们用 自顶向下的方案求解的话，n 的规模可以迅速缩小，比如 n = 10000 ， 只需要执行一步， n = 5000 就可以缩小一半的规模。但是如果用 自底向上的方案，我们需要求出 1 到 10000 的所有子问题的最优解，很显然复杂度太高了。
最优子结构的性质为动态规划解决问题提供了重要的线索。
最优子结构的定义是：问题的最优解是由相关子问题的最优解组合而成，而这些子问题都是可以独立求解的。也就是说一个问题的最优解包含其子问题的最优解。
最优子结构不好理解，我们先来看个反例。
如上图所示，求 A 到 B 的距离 S，S 满足 S % 4 的值最小。
先考虑 B -> D 的距离： 3 + 1 = 4 ， 4 % 4 = 0 如下图所示
如果 A 也按照这个路径走， 那么 A -> D 的路径之和： 2 + 3 + 1 = 6 ， 6 % 4 = 2 。 但实际上 A 应该走的路是 2 + 1 + 1 = 4 。 如下图所示
由此可见，A -> D 的最优路径中，包含的子路径 B -> D 的解并不是最优解。所以，该问题并不具备最优子结构。
最优子结构体现在数学上就是 f(n) 的结果是有 f(1), f(2), f(3) ... ... f(n-1) 组合而成。
由于时间关系，今天暂时发这些。明天继续总结。
联系客服
