算法设计与分析

#

1.课太蠢，简单写一点复习笔记

2.大量的数学笔记都是我复制下来的，我没有手打这么多公式的耐心，只能感谢那名陌生的同学了,原来的仓库https://github.com/DANNHIROAKI/XJTU-CS-Courses/tree/master,可能这篇文章的阅读体验相对会更好一点，因为数学公式会直接渲染并且我会多余做一些补充和更改，如果原作者看到并且觉得这样不好，您可以直接联系我删除。

3.代码就会按照原书中来的，利用Java来实现。

4.https://csdiy.wiki/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/CS170/ 笔者非常后悔在学校老师狂念PPT的时候没有自学这个CS170,如果你还有机会，一定要看一看。

5.关于本课程你理论上能找到两套往年题目，有参考价值，模拟题目参考价值较少，本课程从选修变成必修之后难度应当有所降低，不管你的老师怎么样，考试之前的复习课一定去听，会透露原题。

1.算法概述

#

算法的执行次数和时间都有限。程序不一定，因为有可能有while(true)。

时间复杂性问题

#

O omu o theta

举例子：

f = O(g)

g是f的一个上界，f <= g

omu: >=

o: <

theta: = (既是O 又是omu)

omega: >

n的阶乘

Stirling’s approximation 是对n !趋于无穷速度的估计，公式如下

𝑛!=2𝜋𝑛(𝑛𝑒𝑛)(1+Θ(1𝑛))

可推导：

𝑛!=𝑜(𝑛𝑛) 𝑛!=𝜔(2𝑛) log⁡(𝑛!)=Θ(𝑛log⁡𝑛)

课后题证明以及上下界的练习。

渐进分析的算术运算与证明

应该不难，想办法凑就可以。

常用公式：

•O(f(n))+O(g(n)) = O(max{f(n),g(n)}) ；

•O(f(n))+O(g(n)) = O(f(n)+g(n)) ；

•O(f(n))O(g(n)) = O(f(n)*g(n)) ；

•O(cf(n)) = O(f(n)) ；

•g(n)= O(f(n)) ⇒ O(f(n))+O(g(n)) = O(f(n))

证明示例：以第一个公式举例

•规则O(f(n)) + O(g(n)) = O(max{f(n),g(n)}) 的证明：

•对于任意f1(n)∈ O(f(n)) ，存在正常数c1和自然数n1，使得对所有n ≥ n1，有f1(n)≤c1f(n) 。

•类似地，对于任意g1(n)∈ O(g(n)) ，存在正常数c2和自然数n2，使得对所有n ≥ n2，有g1(n) ≤ c2g(n) 。

•令c3=max{c1, c2}， n3 =max{n1, n2}，h(n)= max{f(n),g(n)} 。

•则对所有的 n ≥ n3，有

•f1(n) +g1(n) ≤ c1f(n) + c2g(n)

≤ c3f(n) + c3g(n)= c3(f(n) + g(n))

≤ c3×2 max{f(n),g(n)}

= 2c3h(n)

则有f1(n) +g1(n)=O(h(n))= O(max{f(n),g(n)})

即O(f(n))+O(g(n)) = O(max{f(n),g(n)})

能搞清楚上下界就没问题。

NP问题

#

应该会考相关的归约的方法。

概括

#

• P：可以“快速解决”的问题（即，多项式时间内能求解）。
• NP：可以“快速验证答案”的问题。
• NPC（NP-Complete，NP 完全）：目前认为“最难的 NP 问题”，一旦能快速解决一个，就能快速解决所有 NP 问题。
• NP-hard（NP 困难）：至少跟 NP 中最难的问题一样难，但本身不一定属于 NP。

解释

#

注意这张图的关系：

P（Polynomial Time）问题

#

• 定义：能在“多项式时间”内求出解的问题。
• 理解方式：你的程序运行时间是 O(n),O(n2),O(n3)O(n), O(n^2), O(n^3)O(n),O(n2),O(n3) 这种（不是指数或阶乘），就属于 P。
• 例子：
  • 排序（冒泡、快排）
  • 最短路径（Dijkstra）
  • 匹配括号是否合法（栈）

NP（Non-deterministic Polynomial Time）问题

#

• 定义：解可以在多项式时间内被验证的问题。
• 关键点：你不一定能很快找到解，但一旦别人告诉你答案，你可以很快验证它对不对。
• 例子：
  • 给一个图，问是否存在一个旅行路径经过所有城市一次？（TSP）
  • 给一个布尔表达式，问是否存在变量组合使其为真？（SAT）

NP 完全（NPC, NP-Complete）

#

• 定义：NP 中最难的问题。
• 满足两个条件：
  1. 本身属于 NP。
  2. 所有 NP 问题都可以在多项式时间归约到它上。
• 通俗理解：它是“NP 阶层中的老大哥”。如果有一天你能快速解决一个 NPC 问题，那你就能快速解决所有 NP 问题（即 P=NPP = NPP=NP）。
• 著名例子：
  • SAT（布尔可满足性问题）
  • TSP（旅行商问题）
  • 3-Coloring（三染色问题）
  • Subset Sum（子集和问题）

NP-hard（NP 困难）

#

注意：NP难问题不一定是NP问题！

• 定义：比 NP 还难的问题（不一定能验证解）。
• 不一定在 NP 类别中，比如不要求答案验证要快。
• 一些 NP-hard 问题甚至不可判定（比如停机问题）。

2.递归和分治策略

#

凡治众如治寡，分数是也。 —-《孙子兵法》

求解采用自顶向下的计算方式。

1.最优子结构。2.小问题可以直接解决。3.最后可以小的问题合并成最终答案。4.子问题之间相互独立。

概念

#

hanoi问题：

设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：

规则1：每次只能移动1个圆盘；

规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；

规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。

void hanoi(int n, int a, int b, int c)
   {
       if (n > 0)
       {
          hanoi(n-1, a, c, b);	//设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c
          move(a,b);			//将塔座a上编号为n的圆盘移到b上
          hanoi(n-1, c, b, a);	//设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b
       }
   }

一般的流程：

void divide-and-conquer(P)
  {
    if ( | P | <= n0) adhoc(P);   					 //解决小规模的问题
    divide P into smaller subinstances P1,P2,...,Pk；//分解问题
    for (i=1,i<=k,i++){
      yi=divide-and-conquer(Pi);
    }												//递归的解各子问题
    return merge(y1,...,yk);  						//将各子问题的解合并为原问题的解
  }

递归的求解

#

​ 一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。

1.递归树法

#

考虑分解和合并的时间：

由于该递归表达式分为两项，所以算树的高度时，我们只需要看n/2的分解，由

𝑛2ℎ=1

可得递归树的层数为

ℎ=log2⁡𝑛

分解的时间消耗为

𝑡1\len2(1+516+25256+…+(516)log2⁡𝑛−1=(516)log2⁡𝑛−1516−1<1611𝑛2

则有

𝑡1=𝑂(𝑛2)

叶子节点小于n个，所以合并就是O（n），那么最终就为t1。

2.主方法

#

令和𝑎≥1和𝑏>1是常数，𝑓(𝑛)是一个函数，𝑇(𝑛)是定义在非负整数上的递归式： 𝑇(𝑛)=𝑎𝑇(𝑛𝑏)+𝑓(𝑛)

T(n) 有如下渐进界：

1️⃣ 若对某个常数 ϵ > 0 有𝑓(𝑛)=𝑂(𝑛log𝑏⁡𝑎−𝜖)，则 T ( n ) = Θ (nlogba)

2️⃣ 若𝑓(𝑛)=Θ(𝑛log𝑏⁡𝑎)，则𝑇(𝑛)=Θ(𝑛log𝑏⁡𝑎lg⁡𝑛)

3️⃣ 若对某个常数 ϵ > 0 有𝑓(𝑛)=Ω(𝑛log𝑏⁡𝑎+𝜖)，且对某个常数𝑐<1和足够大的n有𝑎𝑓(𝑛/𝑏)≤𝑐𝑓(𝑛)则

T ( n ) = Θ ( f ( n ) )

注意点

在第一种情况中，不是𝑓(𝑛)小于𝑛log𝑏⁡𝑎就够了，而是要多项式意义上的小于，也就是说，𝑓(𝑛)必须渐进小于𝑛log𝑏⁡𝑎，要相差一个因子𝑛𝜖。

其中𝜖是大于0的常数。

在第三种情况中，不是𝑓(𝑛)大于𝑛log𝑏⁡𝑎就够了，而是要多项式意义上的大于，而且还要满足"正则"条件𝑎𝑓(𝑛/𝑏)≤𝑐𝑓(𝑛)。遇到的多项式界的函数中，多数都满足这个条件。

此外，这三种情况并非覆盖了𝑓(𝑛)的所有情况，𝑓(𝑛)可能小于𝑛log𝑏⁡𝑎，但不是多项式意义上的小于，也有可能大于但不是多项式意义上的大于，这时候就不能用主方法来求解，而是需要用递归树。

举例说明

#

1️⃣ T (n) = 9 T (n/3) + n

​ 有𝑎=9,𝑏=3,𝑓(𝑛)=𝑛,因此𝑛log𝑏⁡𝑎=𝑛log3⁡9=Θ(𝑛2)，当我们取𝜖=1,有𝑓(𝑛)=𝑂(𝑛log3⁡9−1)，由定理一则有𝑇(𝑛)=Θ(𝑛2)

2️⃣ T (n) = T (2n/3) + 1

​ 有𝑎=1,𝑏=3/2,𝑓(𝑛)=1,因此𝑛log𝑏⁡𝑎=𝑛log3/2⁡1=𝑛0=Θ(1)，由于𝑓(𝑛)=Θ(𝑛log𝑏⁡𝑎)=Θ(1)，由定理二则有𝑇(𝑛)=Θ(lg⁡𝑛)

3️⃣ T (n) = 3 T (n/4) + nlgn

​ 有𝑎=3,𝑏=4,𝑓(𝑛)=𝑛lg⁡𝑛,因此𝑛log𝑏⁡𝑎=𝑛log4⁡3=𝑂(𝑛0.793)，由于𝑓(𝑛)=Ω(𝑛log4⁡3+𝜖)，其中𝜖≈0.2，因此如果可以证明正则条件成立，则可以使用定理三。当n足够大时，对于𝑐=3/4，（𝑎𝑓(𝑛/𝑏)=3（𝑛/4)lg⁡(𝑛/4)≤(3/4)𝑛lg⁡𝑛=𝑐𝑓(𝑛)，由定理二则有𝑇(𝑛)=Θ(𝑛lg⁡𝑛)

⚠️主方法不适用于𝑇(𝑛)+2𝑇(𝑛/2)+𝑛lg⁡𝑛

​ 有𝑎=2,𝑏=2,𝑓(𝑛)=𝑛lg⁡𝑛,因此𝑛log𝑏⁡𝑎=𝑛，𝑓(𝑛)虽然渐进大于n，但是并不是多项式意义上的的大于**(比值要是n的次方)**，对于任意的正常数𝜖，比值𝑓(𝑛)/𝑛log𝑏⁡𝑎=lg⁡𝑛都渐进小于𝑛𝜖，陷入了特殊情况，使用递归树可解决。

可以这么理解，谁大就由谁来决定，相等的情况就是对数和算出来的式子直接做乘法。

分治算法具体问题设计

#

merge and sort

1.二分算法

#

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}

​ 每执行一次算法的while循环，待搜索的数组的大小就减少一半。因此，在最坏情况下，while循环被执行了𝑂(log⁡𝑛)次。循环体内运算需要𝑂(1)时间，因此整个算法在最坏情况下的时间复杂性为𝑂(log⁡𝑛)。

二分代码的纠错，写出bugfree的二分代码，分析七个二分算法的错误。

下标变化错误，会进入死循环。（1 2 3 5 6 7 这个序列中去找数字4）

right控制的有问题，当要查找的数据在最右边的时候就找不到了（1 2 3 5 6 7 中找 7）

和上面是同理的，left + 1 != right 就是 left < right - 1

下标控制错误，left = middle + 1,当要查找的元素为数组中的最后一个的时候，此时陷入死循环。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left) + 1 / 2;
            if(nums[mid] < target){
                left = mid;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                return mid;
            }
        }
        if(target == nums[left]){
            return left;
        }
        return -1;
    }
}

第五个是正确的代码，middle控制的向上作取整可以使得left不用等于middle加1,当有多个重复的时候，取的值是最右边的值。

多了right = mid - 1，这样我们就没办法找到最右边的值了。注意这两个代码都是 left < right 而非相等的。

right = mid，右边的值到不了左边来，那么当你找的数字为第一个元素的时候就会陷入死循环。

从判断错误的角度来讲，举极端例子（找最左边或者最右边），或者数组长度只有1的情况都是很好的方法。

2.大整数乘法

#

处理两个位数很大的数字的乘法：

用类似于因式分解的方法，把原来的两次乘法改成一次乘法，但是只是多了几次加法而已。

3.Strassen矩阵乘法

#

这一部分可以看书，把八次乘法转换成了七次的乘法，和上面的大整数乘法是类似的思想。

4.棋盘覆盖问题

#

​ 在一个2𝑘×2𝑘 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

​ 将2𝑘×2𝑘 棋盘分割为4个2𝑘−1×2𝑘−1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。

​ 解此递归方程可得𝑇(𝑘)=𝑂(4𝑘)，由于覆盖一个2𝑘×2𝑘 棋盘所需要的L型骨牌个数为(4𝑘−1)/3，所以该算法为一个在渐进意义下的最优算法。

5.合并排序（merge sort）

#

​ 基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。

最坏时间复杂度：O(nlogn) 平均时间复杂度：O(nlogn) 辅助空间：O(n)

最坏情况下的时间复杂度：

​ 概念：解此递归方程为𝑇(𝑛)=𝑂(𝑛log⁡𝑛)，由于排序问题的计算时间下界为Ω(𝑛log⁡𝑛)，所以合并排序算法为一个渐进最优算法。

​ 对于算法MergeSort，可以利用分治法消除其中的递归。可以先将数组a中相邻的元素两两配对，用合并算法将他们排序，构成n/2组长度为2的排好序的子数组段，然后再把它们排成长度为4的排好序的子数组段，如此继续下去，直至整个数组排好序。

package Recursion;

public class MergeSort {

    private void sortArray(int[] array) {
        merge(array, 0, array.length - 1);
    }
    private void mergeSort(int[] array, int left, int mid, int right) {
        int[] temp1 = new int[mid - left + 1];
        int[] temp2 = new int[right - mid];
        for (int i = 0; i < temp1.length; i++) {
            temp1[i] = array[left + i];
        }
        for (int i = 0; i < temp2.length; i++) {
            temp2[i] = array[mid + 1 + i];
        }

        int i = 0, j = 0;
        int k = left;
        while (i < temp1.length && j < temp2.length) {
            //注意这里保证了排序的稳定性，小于等于就直接放进去
            if (temp1[i] <= temp2[j]) {
                array[k] = temp1[i];
                ++i;
                ++k;
            }else{
                array[k] = temp2[j];
                ++j;
                ++k;
            }
        }

        while (i < temp1.length) {
            array[k] = temp1[i];
            ++i;
            ++k;
        }
        while (j < temp2.length) {
            array[k] = temp2[j];
            ++j;
            ++k;
        }
    }
    private void merge(int[] array, int left , int right){
        if(left < right){
            int mid = left + (right - left)/2;
            merge(array, left, mid);
            merge(array, mid + 1, right);
            mergeSort(array, left, mid, right);
        }
    }

    public static void main(String[] args) {
        int[] array = {9,8,7,6,5,4,3,2,1};
        MergeSort mergeSort = new MergeSort();
        mergeSort.sortArray(array);
        for(int index = 0; index < array.length; index++){
            System.out.print(array[index] + " ");
        }
    }
}

6.快速排序（Quick Sort）

#

​ 在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。

算法分析如下：

对于输入的子数组a[p:r]，按照以下三个步骤排序：

1️⃣ 分解：以a[p]作为基准元素将a[p:r]分解为三段a[p:q-1],a[q],a[q+1:r]，使a[p:q-1]中的任意一个元素小于等于a[q]，a[q+1:r]中任何一个元素大于等于a[q]，下标在划分过程中确定。

2️⃣ 递归求解：通过递归调用快速排序算法，分别对a[p:q-1]和a[q+1:r]进行排序

3️⃣ 合并：由于对a[p:q-1]和a[q+1:r]的排序使就地进行的，因此排好序后不需要再执行其他计算。

package Recursion;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
        quickSort(arr,0,arr.length-1);
        for(int a:arr){
            System.out.print(a + " ");
        }
    }
    private static void quickSort(int[] arr, int left, int right) {
        if(left < right){
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex-1);
            quickSort(arr, partitionIndex+1, right);
        }
    }
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        while(left < right){
            //找到第一个小于pivot的元素
            while(left < right && arr[right] >= pivot){
                right--;
            }
            //把右边的值移到左边来
            arr[left] = arr[right];
            //找到第一个大于pivot的元素
            while(left < right && arr[left] <= pivot){
                left++;
            }
            //把左边的值移到右边来
            arr[right] = arr[left];
        }
        //最后进行交换
        arr[left] = pivot;
        return left;
    }
}

这里是取第一个元素作为划分的基准，如果取最后一个元素作为基准而且其是数组中最大的元素，那么会陷入死循环。

对于输入序列a[p:r] , Partition的计算时间显然为𝑂(𝑟−𝑝−1)。

​ 快速排序的运行时间与划分是否对称有关,其最坏情况发生在划分过程产生的两个区域分别包含n- 1个元素和1个元素的时候。由于函数Partition的计算时间为𝑂(𝑛),所以如果算法Partition的每一步都出现这种不对称划分,则其计算时间复杂性T(n) 满足

解此递归方程可得𝑇(𝑛)=𝑂(𝑛2)。

​ 在最好情况下,每次划分所取的基准都恰好为中值,即每次划分都产生两个大小为n/2的区域，此时，Partition的计算时间T(n)满足

​ 可以证明,快速排序算法在平均情况下的时间复杂性也是 T ( n ) = O ( n log ⁡ n ) ,这在基于比较的排序算法类中算是快速的,快速排序也因此而得名。

​ 随机选取值而不是每次都选取第一个就可以解决这个问题。

7.线性时间选择

#

⭐ 要能根据代码分析时间复杂度

​ 给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，只需要调用如下方法：RandomizedSelect(a,0,n-1,k)

template<class Type>
Type RandomizedSelect(Type a[],int p, int r, int k){
	if(p==r)
		return a[p];
	int i = RandomizePartition(a,p,r);
	j=i-p+1;
	if(k<=j)
		return RandomizedSelect(a,p,i,k);
	else
		return RandomizedSelect(a,i+1,r,k-j);
}

​ 在算法RandomizedSelect中执行RandomizedPartition后;数组a[p:r]被划分成两个子数组a[p:i]和a[i+1:r],使得中每个元素都不大于a[i+1:r]中每个元素。接着算法计算子数组a[p:i]中元素个数j。如果k≤j,则a[p:r]中第k小元素落在子数组a[p:i]中如果k> j,则要找的第k小元素落在子数组a[i+1:r]中。由于此时已知道子数组a[p:i]中元素均小于要找的第k小元素,因此，要找的a[p:r]中第k小元素是a[i+ 1:r]中的第k- j 小元素。

​ 在最坏情况下,算法RandomizedSelect需要𝑂(𝑛2)计算时间。例如在找最小元素时，总是在最大元素处划分。尽管如此,该算法的平均性能很好。在平均情况下，算法RandomizedSelect可以在𝑂(𝑛)时间内解决⭐

​ 如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0<ε<1是某个正常数)，那么就可以在最坏情况下用O(n)时间完成选择任务。例如，若ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)≤T(9n/10)+O(n) 。由此可得T(n)=O(n)。

寻找划分标准的算法如下：

分组，寻找中位数的中位数，这样的分割位置相对来说比较公平。

​ 1️⃣ 将n个输入元素划分成⌈𝑛/5⌉个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共⌈𝑛/5⌉个。

​ 2️⃣ 递归调用Select来找出这⌈𝑛/5⌉个元素的中位数。如果⌈𝑛/5⌉是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。

​ 设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n/5-1)/2=(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。

template<class Type>
Type Select(Type a[], int p, int r, int k)
{
      if (r-p<75) {
          Sort(Type a[], int p, int r);
        //用某个简单排序算法对数组a[p:r]排序;
        return a[p+k-1];
        };
      for ( int i = 0; i<=(r-p-4)/5; i++ )
         //将a[p+5*i]至a[p+5*i+4]的第3小元素与a[p+i]交换位置;
      Type x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10); //找中位数的中位数，r-p-4即上面所说的n-5
      int i=Partition(a,p,r, x),
      j=i-p+1;
      if (k<=j) return Select(a,p,i,k);
      else return Select(a,i+1,r,k-j);
}

​ 上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=εn，0<ε<1。这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择

时间复杂度分析为：

解得：𝑇(𝑛)=𝑂(𝑛)，要会用递归树求解

看不懂就记住时间复杂度为O（n），考试前再看一下原理，记忆一下数字规律也可以。

8.最近点对问题

#

会写伪代码，典型的简答题。

给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对的距离最小。

​ 为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的n个点退化为x轴上的n个实数 x1,x2,…,xn。最接近点对即为这n个实数中相差最小的2个实数。

​ 假设我们用x轴上某个点m将S划分为2个子集S1和S2 ，基于平衡子问题的思想，用S中各点坐标的中位数来作分割点。递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}，并设d=min{|p1-p2|,|q1-q2|}，S中的最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{p3,q3}，其中p3∈S1且q3∈S2。如果S的最接近点对是{p3,q3}，即|p3-q3|<d，则p3和q3两者与m的距离不超过d，即p3∈(m-d,m]，q3∈(m,m+d]。由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m]中至多包含S中的一个点。由图可以看出，如果(m-d,m]中有S中的点，则此点就是S1中最大点，同理S2这么找就会找到最小的点。因此，我们用线性时间就能找到区间(m-d,m]和(m,m+d]中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。

以下是二维的情况：

​ 选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d2}，S中的最接近点对或者是d，或者是某个{p,q}，其中p∈P1且q∈P2。

考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)＜d。满足这个条件的P2中的点一定落在一个d×2d的矩形R中由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。因此，在分治法的合并步骤中最多只需要检查6×n/2=3n个候选者

⭐ 证明 将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个(d/2)×(2d/3)的矩形。若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个(d/2)×(2d/3)的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则

​ 证明就是六等分，那么一个小矩形的对角边就是最大的长度。

distance(u,v)<d。这与d的意义相矛盾。图b是具有6个S中的点的极端情况。

由上述证明可知，在分治法的合并步骤中，最多只需要检查6xn/2=3n个候选者，而不是n^2/4个。

​ 为了确切地知道要检查哪6个点，可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于d。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。

以下就是伪代码：

double cpair2(S)
{
      n=|S|;
      if (n < 2) return 无穷;
1、m=S中各点x间坐标的中位数;
      //构造S1和S2；
      S1={p∈S|x(p)<=m};
      S2={p∈S|x(p)>m};
      //作递归的处理
2、 d1=cpair2(S1);
    d2=cpair2(S2);
     //找到集合内的最近距离点对，并且记录大小
3、dm=min(d1,d2);
     //预先排序的处理
4、设P1是S1中距垂直分割线l的距离在dm之内的所有点组成的集合；
   P2是S2中距分割线l的距离在dm之内所有点组成的集合；
   将P1和P2中点依其y坐标值排序；
   并设X和Y是相应的已排好序的点列；
    //1对6的扫描找最小值 所以最多是3 * n
5、通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可以完成合并；
  当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动；
  设dl是按这种扫描方式找到的点对间的最小距离；
6、d=min(dm,dl);
      return d;
}

核心过程就是第五步。

​ 下面分析算法Cpair2的计算复杂性。设对于n个点的平面点集S ,算法耗时T(n)。算法的第1步和第5步用了𝑂(𝑛)时间。第3步和第6步用了常数时间。第2步用了2T(n/2)时间。若在每次执行第4步时进行排序,则在最坏情况下第4步要用𝑂(𝑛log⁡𝑛)时间。这不符合我们 的要求。因此，在这里我们采用设计算法时常用的预排序技术,在使用分治法之前,预先将S中n个点依其y坐标值排好序,设排好序的点列为P 。在执行分治法的第4步时,只要对𝑃∗作一次线性扫描,即可抽取出我们所需要的排好序的点列X和Y。然后，在第5步中再对X作一次线性扫描,即可求得dl.因此,第4步和第5步的两遍扫描合在一起只要用0(n)时间。这样,经过预排序处理后算法Cpair2 所需的计算时间T(n)满足递归方程

由此易知, T (n) = O(nlogn) 。预排序所需的计算时间显然为𝑂(𝑛log⁡𝑛)。因此,整个算法所需的计算时间为𝑂(𝑛log⁡𝑛),在渐近的意义下,此算法已是最优算法。

注意考试的时候要写上边界（n = 4）。

3.动态规划

#

基本概念和步骤

#

1、与分治法的异同

#

相同点：都是将求解问题分为若干个子问题

不同点：分治法所要求的子问题是独立的，而动态规划所求解的子问题往往不是独立的，重叠的子问题的多次运算可能会造成指数级的运算量。

2、动态规划的核心思想

#

**记表备查：**保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

3、解题步骤

#

1️⃣ 找出最优解的性质，并刻划其结构特征。

2️⃣ 递归地定义最优值。

3️⃣ 以自底向上的方式计算出最优值。

4️⃣ 根据计算最优值时得到的信息，构造最优解

4、基本要素

#

重叠子问题与最优子结构。

矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。

要证明最优子结构的性质。

最优子结构的证明通常采用反证法，需要掌握。

全局的最优一定有局部的最优，局部的最优不一定会形成全局的最优，必要不充分条件

5、两种基本形态

#

动态规划(自底向上)与备忘录（memo）方法。

备忘录方法是动态规划方法的变形，都是记表备查，不同点在于备忘录方法是自顶向下的递归，而动态规划是自底向上的递归

一般来说，当一个问题的所有子问题都需要至少解一次时，用动态规划算法比用备忘录方法要好

具体问题设计

#

1.*矩阵连乘问题

#

​ 给定n个矩阵𝐴1,𝐴2,…,𝐴𝑛，其中𝐴𝑖与𝐴𝑖+1是可乘的，i=1, 2,…, n-1。考察这n个矩阵的连乘积𝐴1𝐴2…𝐴𝑛。

​ 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。

完全加括号的矩阵连乘积可递归地定义为：

①单个矩阵是完全加括号的；

②矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)

设有四个矩阵A,B,C,D，可以有以下5种不同的加括号方式：

(A(B(CD))) (A((BC)D)) ((AB)(CD)) ((A(BC))D) (((AB)C)D)

​ 每一种完全加括号方式对应于一种矩阵连乘积的计算次序，而矩阵连乘积的计算次序与其计算量有密切关系。矩阵A(p×q)和矩阵B(q×r)的乘积C=AB是一个p×r的矩阵，数乘次数为pqr

❓ 问题：

给定n个矩阵𝐴1,𝐴2,…,𝐴𝑛，其中𝐴𝑖与𝐴𝑖+1是可乘的，i=1, 2,…, n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

1）穷举法

#

计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。

对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1…Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：

这个数字太大，没有计算价值。

2）动态规划法

#

将矩阵连乘积AiAi+1…Aj简记为A[i:j] ，这里i≤j 。

考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k<j，则其相应完全加括号方式为：

(AiAi+1…Ak) (Ak+1Ak+2…Aj)

计算量：A[i:k]的计算量加上A[k+1:j]的计算量，再加上A[i:k]和A[k+1:j]相乘的计算量。

1️⃣ 分析最优解的结构

特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。

矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。

2️⃣ 建立递归关系

设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]。

设Ai的维数为𝑝𝑖−1×𝑝𝑖，则

当i=j时，𝐴[𝑖:𝑗]=𝐴𝑖，因此，m[i,i]=0，i=1,2,…,n

当i<j时，𝑚[𝑖:𝑗]=𝑚[𝑖,𝑘]+𝑚[𝑘+1,𝑗]+𝑝𝑖−1𝑝𝑘𝑝𝑗

可以递归地定义m[i,j]为：

必考问题。

k的位置只有j-i种可能

3️⃣ 计算最优值

对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有

​ 由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征

用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。

代码如下：

public static void matrixChain(int[] p, int[][] dp, int[][] partitionIndex){
        //有n个矩阵
        int n = p.length - 1;
        //初始化为0
        for(int index = 0; index < n; ++index){
            dp[index][index] = 0;
        }
        //控制矩阵链的长度
        for(int len = 2; len <= n; ++len){
           for(int i = 1; i <= n - len + 1; ++i){
               //以第一个为基础
               int j = i + len - 1;
               dp[i][j] = dp[i + 1][j] + p[i + 1] * p[i] * p[j];
               partitionIndex[i][j] = i;
               for(int k = i + 1; k < j; ++k){
                   int value = dp[i][k] + p[i - 1] * p[k] * p[j] + dp[k + 1][j];
                if(value < dp[i][j]){
                    dp[i][j] = value;
                    partitionIndex[i][j] = k;
                }   
               }
           } 
        }
        
    }

​ 算法MatrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为𝑂(1)，而3重循环的总次数为𝑂(𝑛3)。因此算法的计算时间上界为𝑂(𝑛3)。算法所占用的空间显然为𝑂(𝑛2)。

traceback递归地来构造答案，那么完整可运行的代码如下：

package Dynamic;

public class demo01 {
    public static void matrixChain(int[] p, int[][] dp, int[][] partitionIndex){
        //有n个矩阵
        int n = p.length - 1;
        //初始化为0
        for(int index = 0; index < n; ++index){
            dp[index][index] = 0;
        }
        //控制矩阵链的长度
        for(int len = 2; len <= n; ++len){
           for(int i = 1; i <= n - len + 1; ++i){
               //以第一个为基础
               int j = i + len - 1;
               dp[i][j] = dp[i + 1][j] + p[i + 1] * p[i] * p[j];
               partitionIndex[i][j] = i;
               for(int k = i + 1; k < j; ++k){
                   int value = dp[i][k] + p[i - 1] * p[k] * p[j] + dp[k + 1][j];
                if(value < dp[i][j]){
                    dp[i][j] = value;
                    partitionIndex[i][j] = k;
                }
               }
           }
        }

    }

    public static void traceBack(int left, int right, int[][] partitionIndex){
        if(left == right){
            System.out.printf("A" + left);
        }else{
            System.out.print("(");
            traceBack(left, partitionIndex[left][right], partitionIndex);
            traceBack(partitionIndex[left][right] + 1, right, partitionIndex);
            System.out.print(")");
        }
    }

    public static void main(String[] args) {
        int[] p = {30, 35, 15, 5, 10, 20, 25};
        int n = 6;
        int[][] m = new int[7][7];
        int[][] s = new int[7][7];
        matrixChain(p, m, s);
        traceBack(1, 6, s);
        System.out.println();
        System.out.println(m[1][6]);
    }
}

3）备忘录方法

#

memo (python:@cache)

​ 备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。

​ 备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。

​ 用递归解决问题的期间把值记录起来。

以下是代码：

package Dynamic;

public class demo02 {
    public static int lookUpChain(int left, int right, int[] p, int[][] m, int[][] partitionIndex){
        if(m[left][right] > 0){
            return m[left][right];
        }

        if(left == right){
            return 0;
        }

        int min = lookUpChain(left, left, p, m, partitionIndex) + lookUpChain(left + 1, right, p, m, partitionIndex) + p[left - 1] * p[left] * p[right];
        partitionIndex[left][right] = left;
        for(int index = left + 1; index <= right; ++index){
            int curr = lookUpChain(left, index, p, m, partitionIndex) + lookUpChain(index + 1, right, p, m, partitionIndex) + p[left - 1] * p[index] * p[right];
            if(curr < min){
                min = curr;
                partitionIndex[left][right] = index;
            }
        }
        
        m[left][right] = min;
        return min;
    }
}

2.凸多边形最优三角剖分

#

用多边形顶点的逆时针序列表示凸多边形，即P={v0,v1,…,vn-1}表示具有n条边的凸多边形。

若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形{vi,vi+1,…,vj}和{vj,vj+1,…,vi}。

多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。

注意：T中各弦互不相交，且集合T已达到最大；有n个顶点的凸多边形的三角剖分中，恰有n-3条弦和n-2个三角形。

题目描述：给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得该三角剖分中诸三角形上权之和为最小。

① 三角剖分的结构

#

​ 一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积((A1(A2A3))(A4(A5A6)))所相应的语法树如图 (a)所示。凸多边形{v0,v1,…vn-1}的三角剖分也可以用语法树表示。例如，图 (b)中凸多边形的三角剖分可用图 (a)所示的语法树表示。

​ 矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边𝑣𝑖−1𝑣𝑖。三角剖分中的一条弦𝑣𝑖𝑣𝑗，i<j，对应于矩阵连乘积A[i+1:j]。

​ 给定矩阵链𝐴1𝐴2𝐴3𝐴4𝐴5𝐴6，Ai的维数为𝑝𝑖−1×𝑝𝑖；定义凸多边形P={𝑣0,𝑣1,𝑣2,𝑣3,𝑣4,𝑣5,𝑣6}，其三角形𝑣𝑖𝑣𝑗𝑣𝑘上的权函数值为𝑤(𝑣𝑖𝑣𝑗𝑣𝑘)=𝑝𝑖𝑝𝑗𝑝𝑘，依此定义，P的最优三角剖分所对应的语法树给出了矩阵链的最优完全加括号方式。

② 最优子结构性质

#

​ 凸多边形的最优三角剖分问题有最优子结构性质。

证明的时候就要使用反证法。

​ 事实上，若凸(n+1)边形P={v0,v1,…,vn-1}的最优三角剖分T包含三角形v0vkvn，1≤k≤n-1，则T的权为3个部分权的和：三角形v0vkvn的权，子多边形{v0,v1,…,vk}和{vk,vk+1,…,vn}的权之和。可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。因为若有{v0,v1,…,vk}或{vk,vk+1,…,vn}的更小权的三角剖分将导致T不是最优三角剖分的矛盾。

③ 最优三角形剖分的递归结构

#

注意定义的时候前面有一个-1,所以最优方案也是从1开始为t1n

​ 定义𝑡[𝑖][𝑗]，1≤i<j≤n为凸子多边形{vi-1, vi,…,vj}的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化的多边形{vi-1,vi}具有权值0。据此定义，要计算的凸(n+1)边形P的最优权值为𝑡[1][𝑛]。

t  [  i  ]  [  j  ] 的值可以利用最优子结构性质递归地计算。当j-i≥1时，凸子多边形至少有3个顶点。由最优子结构性质，**$t[i][j]$**的值应为$t[i][k]$的值加上$t[k+1][j]$的值，再加上三角形$v_{i-1}v_kv_j$的权值，其中i≤k≤j-1。由于在计算时还不知道k的确切位置，而k的所有可能位置只有j-i个，因此可以在这j-i个位置中选出使值$t[i][j]$达到最小的位置。由此，$t[i][j]$可递归地定义为

那么代码如下，和矩阵乘法是类似的处理方式：

package Dynamic;

public class demo03 {
    public static int w(int a, int b, int c){
        return a * b * c;
    }
    public static void minWeightTriangulation(int[] p, int[][] dp, int n, int[][] partitionIndex){
        //initialize
        for(int index = 1; index <= n; ++index){
            dp[index][index] = 0;
        }
        
        for(int r = 2; r <= n; ++r){
            for(int i = 1; i <= n - r + 1; ++i){
                int j = i + r - 1;
                int minValue = dp[i + 1][j] + w(i - 1, i, j);
                partitionIndex[i][j] = i;
                for(int k = i + 1; k < i + r - 1; ++k){
                    int currValue = dp[i][k] + w(i - 1, j, k) + dp[k + 1][j];
                    if(currValue < minValue){
                        minValue = currValue;
                        partitionIndex[i][j] = k;
                    }
                }
            }
        }
    }
}

3.多边形游戏

#

​ 多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。

1️⃣ 游戏第1步，将一条边删除。

2️⃣ 随后n-1步按以下方式操作：

(1)选择一条边E以及由E连接着的2个顶点V1和V2；

(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。

3️⃣ 最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。

先只作证明，具体可以看书。

4.公园游艇问题(考试难度类似)

#

​ 题目描述：长江游艇俱乐部在长江上设置了n 个游艇出租站{1,2,…,n}。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金为r(i,j),1≤i<j≤n。试设计一个算法，计算出从游艇出租站 1 到游艇出租站 n 所需的最少租金。

思考一下，还是和矩阵连乘的问题是类似的。

1️⃣ 最优解结构

​ r(i,j)表示游艇出租站i直接到j之间的租金，m(i,j)表示从出租站i出发，到达第j站需要的租金 例如m(1,3)就表示从第1站出发，到达第3站所需的租金，而m(1,3)可以有多种租用方案，例如可以1-2.2-3与1-3。

假设在第k站换游艇( i ≤ k ≤ j ) ,则有m(i,j)=m(i,k)+m(k,j)，其中m(i,j)的最优解包括m(i,k)与m(k,j)的最优解。

2️⃣ 建立递归关系

由以上分析可知，显然有：

3️⃣ 计算最优值

    void cent(int[][] m, int n, int[][] s) {
       for (int i = 1; i <=n ; i++) {
            m[i][i]=0;
        }
        for (int r = 2; r <= n; r++)
            for (int i = 1; i <= n - r + 1; i++) {
                int j = i + r - 1;
                s[i][j] = i;
                for (int k = i; k <= j; k++) {
                    int temp = m[i][k] + m[k][j];
                    if (temp < m[i][j]) {
                        m[i][j] = temp;
                        s[i][j] = k;//在第k站下
                    }
                }
            }
    }

构造最优解：

void traceBack(int i, int j, int[][] s) {
    if (i == j) {
        System.out.print(i);
        return;
    }
    System.out.print("[");
    traceBack(i, s[i][j], s);
    traceBack(s[i][j] + 1, j, s);
    System.out.print("]");
}

5.最大子段和

#

和最大的一个连续子数组。

​ LeetCode：https://leetcode.cn/problems/maximum-subarray/description/

​ 题目描述：给定由n个整数（可能为负整数）组成的序列a1,a2,…,an，求该序列子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依此定义，所求的最优值为：

例，序列{-2,11,-4,13,-5,-2}的最大子段和为20。

​ 做法：定义状态 f[i] 表示以 a[i] 结尾的最大子数组和，不和 i 左边拼起来就是 f[i]=a[i]，和 i 左边拼起来就是 f[i]=f[i−1]+a[i]，取最大值就得到了状态转移方程 f[i]=max(f[i−1],0)+a[i]，答案为 max(f)。这个做法也叫做 Kadane 算法。

由b[j]的定义易知，当b[j-1]>0时，b[j]=b[j-1]+a[j]，否则b[j]=a[j]，故

代码如下：

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        for(int index = 1; index < n; ++index){
            if(dp[index - 1] < 0){
                dp[index] = nums[index];
            }else{
                dp[index] = dp[index - 1] + nums[index];
            }
            ans = Math.max(ans, dp[index]);
        }
        return ans;
    }
}

最大子段和问题与动态规划算法的推广

#

1、最大子矩阵和问题

#

给定一个m行n列的整数矩阵A，试求矩阵A的一个子矩阵，使其各元素之和为最大。

把每两行之间的数字相加起来，使之成为一个一维的数组，接着用上面的方法来处理即可，这个问题比较简单。

    /**
     * 最大子矩阵和
     * @param m
     * @param n
     * @param a
     * @return
     */
   public static int MaxSum2(int m,int n,int[][]a){
        int sum=0;
        int[]b=new int[n];
        for(int i=0;i<m;i++){  //从第i行
            for(int k=0;k<n;k++)  //初始化数组b
                b[k]=0;
            for(int j=i;j<m;j++){  //到第j行
                for(int k=0;k<n;k++)
                    b[k]+=a[j][k];//按列取值
                int max=solveByDP(b);
                if(max>sum)
                    sum=max;
            }
        }
        return sum;
    }

2.*最大M子段和问题

#

​ 定由n个整数（可能为负数）组成的序列{a1,a2,…,an}，以及一个正整数m，要求确定序列{a1,a2,…,an}的m个不相交子段，使这m个子段的总和达到最大。

设b(i,j)表示数组a的前j项中i个子段和的最大值，且第i个子段含a[j]（1≤i ≤ m，i ≤j ≤n），则计算b(i,j)的递归式为

初始时

b(0,j)=0, (1≤j ≤n)

b(i,0)=0, (1≤i ≤m)

int MaxSum(int m,int n,int *a)
{
    if(n<m||m<1)
        return 0;
    int **b=new int *[m+1]; //定义二维数组b
    for(int i=0; i<=m; i++)
        b[i]=new int[n+1];
    for(int i=0; i<=m; i++)   //初始值
        b[i][0]=0;
    for(int j=1; j<=n; j++)
        b[0][j]=0;
	for(int i=1; i<=m; i++)  //1≤i ≤m
        for(int j=i; j<n-m+i; j++)  //j≥i, t<j
            if(j>i)
            {
                b[i][j]=b[i][j-1]+a[j];
                for(int k=i-1; k<j; k++)   //i-1≤t<j
                    if(b[i][j]<b[i-1][k]+a[j])
                        b[i][j]=b[i-1][k]+a[j];
            }
            else  //j=i, 每个数都是一个子段
                b[i][j]=b[i-1][j-1]+a[j];
    int sum=0;
    for(int j=m; j<=n; j++)
        if(sum<b[m][j])
            sum=b[m][j];
    return sum;
}

6.*图像压缩问题（没看懂）

#

我没看懂在干嘛，先放着吧。

​ 计算机中常用像素点灰度值序列{𝑝1,𝑝2,…,𝑝𝑛}表示图像，𝑝𝑖表示像素点i的灰度值。灰度值的范围常为0~255，需要用8位来表示。

​ 图像的变位压缩存储格式将所给的像素点序列{𝑝1,𝑝2,…,𝑝𝑛}分割成m个连续段{𝑆1,𝑆2,…,𝑆𝑚}。第i个像素段Si中有l[i]个像素，且该段中每个像素都只用b[i]位表示。需用3位表示b[i]，如果限制1≤l[i]≤255，则需要用8位表示l[i]，因此第i个像素段所需的存储空间为l[i]*b[i]+11。——即一段中最多有255个像素，用8位二进制表示

整个像素序列的存储空间为

问题描述：确定像素序列{p1,p2,…,pn}的一个最优分段，使得依此分段所需的存储空间最小。其中0≤pi ≤255，1 ≤i ≤n，每个分段的长度不超过255位。

1️⃣ 最优子结构

#

设l[i],b[i]，1≤i ≤m是{𝑝1,𝑝2,…,𝑝𝑛}的最优分段。显而易见，l[1],b[1]是{𝑝1,𝑝2,…,𝑝𝑙[1]}的最优分段，且l[i],b[i]， 2≤i ≤m是

{𝑝𝑙[1]+1,…,𝑝𝑛}的最优分段。即图象压缩问题满足最优子结构性质。

2️⃣ 递归计算最优值

#

设s[i]，1≤i≤n，是像素序列{𝑝1,𝑝2,…,𝑝𝑖}的最优分段所需的存储位数。由最优子结构性质易知：

举例：

3️⃣ 构造最优解

#

算法用l[i],b[i]记录了最优分段所需的信息。

最优分段的最后一段的段长和像素位数分别存储于l[n]和b[n]中，其前一段的段长度和像素位数存储于l[n-l[n]]和b[n-l[n]]中。依此类推，可在O(n)时间内构造出相应的最优解

    /**
     * 计算十进制数i所需的二进制位数
     *
     * @param i
     * @return
     */
    static int length(int i) {
        int k = 1;
        i = i / 2;
        while (i > 0) {
            k++;
            i = i / 2;
        }
        return k;
    }

    /**
     * @param n
     * @param l [p1:pi]的最优分段中最后1个分段的像素个数
     * @param p p[p1:pn]，像素点灰度值序列
     * @param s 像素序列[p1:pi]的最优分段所需的存储位数
     * @param b 像素p[i]所需的存储位数
     */
    public static void Compress(int n, int[] p, int[] s, int[] l, int[] b) {
        int Lmax = 255;//每个分段的长度不超过255位
        int header = 11;//分段段头所需的位数,表示一个段的附加信息
        s[0] = 0;
        for (int i = 1; i <= n; i++) //[p1:pi]
        {
            b[i] = length(p[i]);
            int bmax = b[i];
            s[i] = s[i - 1] + bmax; //k=1
            l[i] = 1;
            for (int j = 2; j <= i && j <= Lmax; j++) //最后的1个分段中有j个像素
            {
                if (bmax < b[i - j + 1])
                    bmax = b[i - j + 1];//这一段中的最大位数
                if (s[i] > s[i - j] + j * bmax) {//找到更好的分段
                    s[i] = s[i - j] + j * bmax;
                    l[i] = j;
                }
            }
            s[i] += header;//加上额外开销
        }
    }


    public static int Traceback(int n, int i, int[] s, int[] l) {
        if (n == 0)
            return i;
        i = Traceback(n - l[n], i, s, l);
        s[i++] = n - l[n];// 重新为s[]数组赋值，用来存储分段位置
        return i;
    }

    static void Output(int s[], int l[], int b[], int n) {
        System.out.println("The optimal value is " + s[n]);
        int m = 0;
        m=Traceback(n, m, s, l);  //m:分段数
        s[m] = n;  //m个分段像素的累积和，Traceback算到m-1个
        System.out.println("Decompose into " + m + " segments");
        for (int j = 1; j <= m; j++) {
            l[j] = l[s[j]]; //计算第j个分段像素个数: l[j]
            b[j] = b[s[j]];  //计算第j个分段所需的存储位数: b[j]
        }
        for (int j = 1; j <= m; j++)
            System.out.println(l[j] + " " + b[j]);
    }


    public static void main(String[] args) {
        int p[] = {0,10,12,15,255,2,1};//第一位不算
        int N=p.length;
        int s[] = new int[N];
        int l[] = new int[N];
        int b[] = new int[N];
        Compress(N-1, p, s, l, b);
        Output(s, l, b, N-1);
    }
}