我们已经看到了一些优雅的设计原则，例如分而治之，图探索和贪婪的选择，它们为各种重要的计算任务提供了确定的算法。这些工具的缺点是只能用于非常特定类型的问题。现在我们来谈谈算法工艺的两个大锤，即动态编程和线性编程，这两种适用性非常广泛的技术可以在更专门的方法失败时调用。可以预见的是，这种普遍性通常会带来效率上的损失。

很多经典的方法，如 divide-and-conquer, graph exploration, and greedy等, 为各种重要的计算任务提供了确定性的解法。但是这些算法只能用于特定类型的问题。

这里介绍两个算法大杀器: Dynamic programing 和 linear programming.

这两种适用性非常广的算法可以在黔驴技穷时考虑调用（如 the knapsack problem, sequence alignment, and optimal binary search trees）。当然，普遍性往往会带来效率上的损失。

动态规划

动态规划作为一种编程范例，可以从一个例子着手理解：求数列的 maximum-weighted independent sets (MIS, 最大非连续非相邻子集)和, 对于a = [1, 4, 5, 4], 其MIS为{a[1], a[3]} = 8.

如果使用贪心法, 每次都在可选范围内取最大值, 那么就会得到{a[2], a[0]} = 6.

如果使用分而治之法, 把数组分为两半a1 = [1, 4], a2 = [5, 4], 则分别得到MIS{a1[1]}, {a2[0]}, 合并后发现是相邻的, 与要求相悖.

要解决这个问题，关键的步骤是找到基于子问题最优解的最优解：想办法把缩小最优解备选方案的数量，在这个较小的空间中可以直接采取暴力搜索寻找最优解。

对于a = [1, 4, 5, 4], 假设其MIS为S, 假如从最右边的元素开始考虑, a[3] = 4只有属于S和不属于S两种情况

  • 若a[3] = 4属于S: 那么a[2] = 5就肯定不属于S, 则S1 = MIS([1, 4]) + MIS([4])
  • 若a[3]不属于S: 那么S只能存在于[1, 4, 5]中, 问题就变成S2 = MIS([1, 4, 5])

所以归纳出S = max(S1, S2) = max(MIS([1, 4]) + MIS([4]), MIS([1, 4, 5])) = ...。 对于只剩下一个元素的去情况, MIS([4]) = max(4) = 4, 即MIS([i]) = i

这就是一个递归的调用: 也就是从右往左, 每一个元素都要考虑一遍是否属于S, 每次会分裂出两种情况, 所以递归的复杂度是$Θ(2^n)$.

这个算法效率不高, 需要优化. 我们考虑这个问题到底有多少不同的子问题? 因为我们是从右往左扫描每一个元素, 对于每一个元素i, 不管其属于或不属于S, 待解决的递归子问题只有一个, 就是求其左边的所有元素(前缀)的MIS, 所以理论上有$Θ(n)$个不同的子问题.

所以虽然递归的调用是$Θ(2^n)$, 但需要解决的子问题只有$Θ(n)$, 那么就存在优化的空间. 办法就是通过记忆已经解决了的子问题的答案, 来避免重复的计算. 因为右边的元素的子问题答案需要用到其左边的子问题的答案, 所以计算时, 要从左往右计算.

定义子问题: 用MIS(i)表示a[i]的前缀a[: i]的MIS(不包括a[i]),

  1. MIS(0) = 0, 因为a[0]左边没有任何元素.
  2. MIS(1) = max(a[0:1]) = a[0]
  3. 对于i > 1, MIS(i)只有两种情况, 取二者中较大者:
    1. 包括a[i - 1], MIS(i) = MIS(i - 2) + a[i - 1]
    2. 不包括, MIS(i) = MIS(i - 1)

从开头开始考虑(计算), 每一步i都记住对应子问题的最优解MIS(i), 计算到最后一个子问题MIS(N), 就得出了考虑了所有子问题之后的最大值

public static int[] forwardMIS(int[] a) {
    int[] mis = new int[a.length + 1];
    mis[0] = 0;
    mis[1] = a[0];
    for (int i = 2; i < mis.length; i++) {
        mis[i] = Math.max(mis[i - 1], mis[i - 2] + a[i - 1]);
    }
    return mis;
}

但以上算法并没有记录MIS具体包含哪些子集，虽然可以通过修改mis数据结构来额外存储每个值对应的MIS点集, 但这样会影响效率而且浪费内存空间.

回忆前面从右往左的分析, 每个元素都会考量是否属于MISS, 所以我们可以把forwardMIS中算好的mis数组从右往左依次判断一遍, 已决定是否把a对应位置的元素加入到S中.

public static ArrayList<Integer> backwardMIS(int[] a) {
    ArrayList<Integer> s = new ArrayList<>();
    int i = mis.length - 1;
    while (i >= 2) {
        if (mis[i - 1] >= mis[i - 2] + a[i - 1]) {
            i--;
        } else {
            s.add(a[i - 1]);
            i -= 2;
        }
    }
    return s;
}

进一步优化，我们可以用类似backward的算法一次过(O(n))计算出MIS的集合和MIS的值, 对backward算法稍作改动, 在a表末尾延申一个0元素, 然后从右往左依次判断一遍, 直接用a表自身的值来判断, 得到一个Backward算法:

static int sum = 0;
public static ArrayList<Integer> backwardMISI(int[] a) {
    ArrayList<Integer> s = new ArrayList<>();
    int i = a.length - 2; // assume a = [a, 0]
    while (i >= 0) {
        int x = get(a, i);
        if (get(a, i + 1) >= get(a, i + 2) + x) {
            i--;
        } else {
            s.add(x);
            sum += x;
            i -= 2;
        }
    }
    return s;
}

private static int get(int[] a, int index) {
    if (index > a.length -1) {
        return 0;
    } else {
        return a[index];
    }
}

总结动态规划的解法：

  • 定义合适的子问题集合: 这些子问题应该尽可能小，数量尽可能少。因为即使在最好的情况下，也要花费 constant time 来解决每个子问题，因此子问题的数量和大小就是整个算法运行时间的下限。
  • 归纳转移方程：系统地解决从最小的子问题开始的所有子问题后，如何转向越来越大的子问题。
  • 通过记忆减少重复的递归调用计算: 要求前面子问题的解决方案能够用来快速计算当前子问题。

参考资料