Solve

编程珠玑第八章探讨

这一章节给出的问题让人从直觉上判断就是动态规划。不过，本章的分治算法也非常的巧妙，他们的优势都是避免了一些重复计算。动态规划本质也就是对于穷举法的优化。作者在指出这些算法时，由简单到困难的描述了复杂的算法有时能让效率大幅提高。对于O(n^2)的暴力来说，O(nlogn)的分治算法的确印证了这一点。但是O(n)的动态规划却不算复杂，相反，比起暴力他还来的简单些。而除了这道特定的题目以外，其他凡是用到DP的地方都能够反映出动态规划的简洁美，不失为一种优美且高效精巧的解决方案。

复杂深奥的算法有时可以极大地提高程序性能

问题探讨

书中围绕着最大连续子串和分析了暴力，分治和DP的不同解决方案。这个问题是提出者对于二维模型的简化版本。我们可以只管判断，因为我们至少要扫描完整个子串才能断定最大的子串，所以这个算法的时间复杂度下界至少不小于O(n)：

先给出O(nlogn)的改进分治算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int maxsum(int left, int right){
    if (left > right) return 0;
    if (left == right) return MAX(num[left], 0);
    int mid = (left + right) / 2;
    lmax = sum = 0;
    lrec = mid;
    rrec = mid + 1;
    for(int i = mid; i >= left; i--){
        sum += num[i];
        if(sum > lmax){
            lmax = sum;
            lrec = i;
        }
    }
    rmax = sum = 0;
    for(int i = mid + 1; i <= right; i++){
        sum += num[i];
        if(sum > rmax){
            rmax = sum;
            rrec = i;
        }
    }
    return MAX(MAX(lmax + rmax, maxsum(left, lrec)), maxsum(rrec, right));
}

然后是DP：

1
2
3
4
for(int i = 1; i <= n; i++){
    temp = MAX(temp + num[i], 0);
    ans = MAX(temp, ans);
}

4.试验表明，不是太容易看出来，取决于串的长度。

10.这道题目其实需要对判别条件做出理解，原本是MAX，我们要把这个MAX改为最接近0。但是其实我们可以得到任一区间的和，用累加数组num，那么从i到j的和就是num[j] - num[i - 1]，我们要求的就是num[j] - num[i - 1]最小。显然两个值越接近，他们的差就越小。直接找需要O(n^2)的复杂度，所以我们排个序，然后遍历找到最小的区间，O(nlogn)。

13.问题要求是求出矩形的数组，势必需要对行或者列进行遍历扫描。我们先划定一个维度，比如行。我们每次无重复的处理i到j行，所有的组合需要n^2的复杂度。然后每一对行组合，比如i1到j1行已经界定后，我们可以把它看成是一维的，用动态规划去处理。总的复杂度O(n^2m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i = 1; i <= n; i++){
    memset(col, 0, sizeof(col));
    for(int j = i; j <= n; j++){
        for(int k = 1; k <= m; k++)
            col[k] += num[j][k];
        temp = 0;
        tot = 0;
        for(int k = 1; k <= m; k++){
            temp = MAX(temp + col[k], 0);
            tot = MAX(tot, temp);
        }
        ans = MAX(ans, tot);
    }
}
  1. T(1) = 0时，T(n) = 2nc。T(1) = c时，T(n) = nlognc。这里面有一定的启示，刚好印证着分治算法和动态规划的时间复杂度关系。

摘录

本章故事中的这些算法给出了几个重要的算法设计技术。

  • 保存状态，避免重复计算。算法2和算法4使用了简单的动态规划。通过使用一些空间来保存中间计算结果，我们避免了花时间对其重复计算。
  • 将信息预处理至数据结构中。算法2b中得cumarr结构允许对子向量中的总和进行快速计算。
  • 分治算法。算法3使用了简单地分治算法形式；有关算法设计的教科书介绍了更高级的分治算法形式。
  • 扫描算法。与数组相关的问题经常可以通过思考“如何将x[0..i-1]的解扩展为x[0..i]的解”来解决。算法4通过同时存储已有的答案和一些辅助数据来计算新答案。
  • 累积。算法2b使用了一个累积表，表中第i个元素的值为x中前i个值的总和；这一类表常用于处理有范围限制的问题。例如，业务分析师要确定3月份到10月份的销售额，可以从10月份的本年迄今销售额中减去2月份的销售额。
  • 下界。只有在确定了自己的算法是所有可能算法中最佳的算法以后，算法设计师才可能踏踏实实地睡个好觉。为此，他们必须证明某个相匹配的下界。对问题线性下界的讨论见习题6，更复杂的下界证明可能会十分困难。