理解贪心算法

贪心算法是使所做的选择看起来都是当前最佳的，期望通过所做的局部最优选择来产生一个全局最优解。

设计贪心算法的步骤：

1.将优化问题转换成这样一个问题，即先做出选择，再解决剩下的一个子问题。

2.证明原问题总是有一个最优解是贪心选择的得到的，从而说明贪心选择的安全。

3.说明在做出贪心选择后，剩下的子问题具有这样一个性质。即如果将子问题的最优解和我们所做的贪心选择联合起来，可以得到一个更加负责的动态规划解。

剪绳子问题描述：

给你一个长度为n的绳子，请把绳子剪成m段（m，n都是整数，且都大于1）每段绳子的长度即为K[0],K[1],K[2]...K[m]。请问K[0]*k[1]..*k[m]可能的最大乘积是多少？

解决思路：

如果我们按照如下的策略剪绳子,则得到的各段绳子的长度的乘积将最大;当n>=5,我们尽可能地剪长度为3的绳子;当剩下的绳子长度为4时,把绳子剪为长度为2的绳子.

贪心算法的核心是通过局部最优解来得到全局最优解,对于分割问题来说,要使乘积最大,该问题的贪心思想是尽可能去剪为长度为3的绳子!

Java迭代法：

public static int greedy_cut_rope_1(int n)
{
    if(n<2)
        return 0;
    if(n==2)
        return 1;
    if(n==3)
        return 2;
    //尽可能多地去减长度为3的绳子段
    int timesOf3 = n/3;
    //当绳子最后剩下的长度为4的时候，不能再去剪去长度为3的绳子段
    if(n-timesOf3*3==1)
        timesOf3-=1;
    int timesOf2 =(n-timesOf3*3)/2;
    return (int) (Math.pow(3,timesOf3)*Math.pow(2,timesOf2));
}

Java递归法：

public static int greedy_cut_rope(int n)
{
    if(n==2)
        return 2;
    if(n==3)
        return 3;
    if(n<2)
        return 1;
    //int timesOf3 = n/3;
    if(n==4)
        return 4;
    return 3*greedy_cut_rope(n-3);
}

背包问题描述：

给定N个物品和一个容量为C的背包,物品i的重量为Wi，其价值为Vi，背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大。注意在背包问题中，可以将某种物品的一部分装入背包中，但是不可以重复装入。

三种贪心思想：

选择价值最大的物品
选择重量最轻的物品
选择单位重量价值最大的物品

毫无疑问，我们当然选择第三种咯。先把性价比最高的全部装入，最后不足全部装入的部分装入。

public static int greedy_knapSack(int[] w,int[] v,int n,int c)
{
    //  假设物品已按单位重量降序排列
    double[] x = new double[10];
    int maxValue =0;
    int i;
    for(i=0;w[i]<c;i++)
    {
        x[i]=1; //将物品 i 装入背包
        maxValue+=v[i];
        c=c-w[i]; // 背包剩余数量
    }
    x[i]=(double)c/w[i];    //物品i装入一部分
    maxValue+=x[i]*v[i];
    return maxValue;    //返回背包获得的价值
}

活动选择问题

假设有一个需要使某一资源的n个活动组成的集合S={a1，a2，a3...an}。该资源一次只能被一个活动占用，每个活动ai有一个开始时间Si和结束时间Fi，且0<=Si<Fi<∞。一旦被选择后，活动ai就占据半开时间区间[Si,Fi)。如果区间[Si，Fi)与 [Sj，Fj)互不重叠，称活动ai与aj是兼容的。活动选择问题就是要选择出一个由互相兼容的问题组成的最大集合。

解决思路

对于任意非空子问题Sij，设am是Sij中具有最早结束时间的活动：

fm=min{fk:ak∈Sij}

那么：

1.活动am在Sij的某最大兼容活动子集中被使用。

2.子问题Sim为空，所以选择am使子问题Smj为唯一可能非空的子问题

在解决子问题时，选择am是一个可被合法调度、具有最早结束时间的活动。从直觉上来看，这种活动选择方法是一种贪婪技术，他给后面剩下的待调度任务留下了尽可能多的机会。也就是说，此处的贪心选择使得剩下的、未调度的时间最大化。

Java实现代码

迭代贪心算法

public static void greedy_activity_selector(int[] s,int[] f,boolean[] b)
{
    int n = s.length-1;
    b[1]=true;
    int j=1;
    for(int i =2;i<=n;i++)
    {
        if(s[i]>f[j])
        {
            b[i]=true;
            j=i;
        }else
            b[i]=false;
    }
    for(int i=1;i<b.length;i++)
        System.out.println(b[i]);
}

总述
1、求解思路：把问题分解为多个子问题，只要依次求出子问题的最优解，就能得到最终问题的最优解。即，只需要考虑局部最优，就能得到全局最优。
2、局限性：需要先确认一个问题具有上述特点，才能使用贪心算法求解。

适用场景
1、单源最短路经问题
2、最小生成树问题
3、可任意分割的背包问题。如果不可以任意分割，就需要用动态规划求解。
4、某些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
5、活动安排

设有N个活动时间集合，每个活动都要使用同一个资源，比如说会议场，而且同一时间内只能有一个活动使用，每个活动都有一个使用活动的开始si和结束时间fi，即他的使用区间为（si,fi）,现在要求你分配活动占用时间表，即哪些活动占用该会议室，哪些不占用，使得他们不冲突，要求是尽可能多的使参加的活动最大化，即所占时间区间最大化！

回溯法

概念：

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

基本思想：

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

回溯步骤：

（1）针对所给问题，确定问题的解空间：

首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。

（2）确定结点的扩展搜索规则

（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

算法框架：

（1）问题框架

设问题的解是一个n维向量(a1,a2,………,an),约束条件是ai(i=1,2,3,…..,n)之间满足某种条件，记为f(ai)。

（2）非递归回溯框架

 int a[n],i;
 初始化数组a[];
 i = 1;
 while (i>0(有路可走)   and  (未达到目标))  // 还未回溯到头
 {
     if(i > n)                                              // 搜索到叶结点
     {   
           搜索到一个解，输出；
     }
     else                                                   // 处理第i个元素
     { 
           a[i]第一个可能的值；
           while(a[i]在不满足约束条件且在搜索空间内)
           {
               a[i]下一个可能的值；
           }
           if(a[i]在搜索空间内)
          {
               标识占用的资源；
               i = i+1;                              // 扩展下一个结点
          }
          else 
         {
               清理所占的状态空间；            // 回溯
               i = i –1; 
          }
 }

（3）递归的算法框架

回溯法是对解空间的深度优先搜索，在一般情况下使用递归函数来实现回溯法比较简单，其中i为搜索的深度，框架如下：

int a[n];
 try(int i)
 {
     if(i>n)
        输出结果;
      else
     {
        for(j = 下界; j <= 上界; j=j+1)  // 枚举i所有可能的路径
        {
            if(fun(j))                 // 满足限界函数和约束条件
              {
                 a[i] = j;
               ...                         // 其他操作
                 try(i+1);
               回溯前的清理工作（如a[i]置空值等）;
               }
          }
      }
 }

回溯法有通用解题法之称，可以系统地搜索问题的所有解，回溯法是一个既带有系统性又带有跳跃性的搜索算法。

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

回溯法的解题步骤：

(1)针对所给问题，定义问题的解空间；

(2)确定易于搜索的解空间结构；

(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

子集树与排列树

下面的两棵解空间树是回溯法解题时常遇到的两类典型的解空间树。

(1)当所给问题是从n个元素的集合S中找出S满足某种性质的子集时，相应的解空间树称为子集树。例如从n个物品的0-1背包问题(如下图)所相应的解空间树是一棵子集树，这类子集树通常有2^n个叶结点，其结点总个数为2^(n+1)-1。遍历子集树的算法需Ω(2^n)计算时间。

(2)当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。例如旅行售货员问题(如下图)的解空间树是一棵排列树，这类排列树通常有n!个叶结点。遍历子集树的算法需Ω(n!)计算时间。

用回溯法搜索子集树的一般算法可描述为：

/** 
 * output(x)     记录或输出得到的可行解x 
 * constraint(t) 当前结点的约束函数 
 * bount(t)      当前结点的限界函数 
 * @param t  t为当前解空间的层数 
 */  
void backtrack(int t){  
    if(t >= n)  
        output(x);  
    else  
        for (int i = 0; i <= 1; i++) {  
            x[t] = i;  
            if(constraint(t) && bount(t))  
                backtrack(t+1);  
        }  
}

用回溯法搜索排列树的一般算法可描述为：

/** 
 * output(x)     记录或输出得到的可行解x 
 * constraint(t) 当前结点的约束函数 
 * bount(t)      当前结点的限界函数 
 * @param t  t为当前解空间的层数 
 */  
void backtrack(int t){  
    if(t >= n)  
        output(x);  
    else  
        for (int i = t; i <= n; i++) {  
            swap(x[t], x[i]);  
            if(constraint(t) && bount(t))  
                backtrack(t+1);  
            swap(x[t], x[i]);  
        }  
}

回溯法的应用例子

(a)子集树

I.输出集合S中所有的子集，即limit为all；

II.输出集合S中限定元素数量的子集，即limit为num；

III.输出集合S中元素奇偶性相同的子集，即limit为sp。

public class Subset {  
          
    private static int[] s = {1,2,3,4,5,6,7,8};  
    private static int n = s.length;  
    private static int[] x = new int[n];  
      
    /** 
     * 输出集合的子集 
     * @param limit  决定选出特定条件的子集 
     * 注：all为所有子集,num为限定元素数量的子集, 
     *    sp为限定元素奇偶性相同，且和小于8。 
     */  
    public static void all_subset(String limit){  
        switch(limit){  
        case "all":backtrack(0);break;  
        case "num":backtrack1(0);break;  
        case "sp":backtrack2(0);break;  
        }  
    }  
      
  
    /** 
     * 回溯法求集合的所有子集，依次递归 
     * 注：是否回溯的条件为精髓 
     * @param t 
     */  
    private static void backtrack(int t){  
        if(t >= n)  
            output(x);  
        else  
            for (int i = 0; i <= 1; i++) {  
                x[t] = i;  
                backtrack(t+1);  
            }  
          
    }  
      
    /** 
     * 回溯法求集合的所有(元素个数小于4)的子集，依次递归 
     * @param t 
     */  
    private static void backtrack1(int t){  
        if(t >= n)  
            output(x);  
        else  
            for (int i = 0; i <= 1; i++) {  
                x[t] = i;  
                if(count(x, t) < 4)  
                    backtrack1(t+1);  
            }  
          
    }  
  
    /** 
     * (剪枝) 
     * 限制条件：子集元素小于4,判断0~t之间已被选中的元素个数， 
     *        因为此时t之后的元素还未被递归,即决定之后的元素 
     *        是否应该被递归调用 
     * @param x 
     * @param t 
     * @return 
     */  
    private static int count(int[] x, int t) {  
        int num = 0;  
        for (int i = 0; i <= t; i++) {  
            if(x[i] == 1){  
                num++;  
            }  
        }  
        return num;  
    }  
  
    /** 
     * 回溯法求集合中元素奇偶性相同，且和小于8的子集,依次递归 
     * @param t 
     */  
    private static void backtrack2(int t){  
        if(t >= n)  
            output(x);  
        else  
            for (int i = 0; i <= 1; i++) {  
                x[t] = i;  
                if(legal(x, t))  
                    backtrack2(t+1);  
            }  
          
    }  
      
    /** 
     * 对子集中元素奇偶性进行判断，还需元素的数组和小于8 
     * @param x 
     * @param t 
     * @return 
     */  
    private static boolean legal(int[] x, int t) {  
        boolean bRet = true;   //判断是否需要剪枝  
        int part = 0;  //奇偶性判断的基准  
          
        for (int i = 0; i <= t; i++) {  //选择第一个元素作为奇偶性判断的基准  
            if(x[i] == 1){  
                part = i;  
                break;  
            }  
        }  
          
        for (int i = 0; i <= t; i++) {  
            if(x[i] == 1){  
                bRet &= ((s[part] - s[i]) % 2 == 0);  
            }  
                  
        }  
  
        int sum = 0;  
        for(int i = 0; i <= t; i++){  
            if(x[i] == 1)  
                sum += s[i];  
        }  
        bRet &= (sum < 8);  
              
        return bRet;  
    }  
  
  
    /** 
     * 子集输出函数 
     * @param x 
     */  
    private static void output(int[] x) {  
        for (int i = 0; i < x.length; i++) {  
            if(x[i] == 1){  
                System.out.print(s[i]);  
            }  
        }  
        System.out.println();     
    }  
  
}

(b) 排列树

I.输出集合S中所有的排列，即limit为all；

II.输出集合S中元素奇偶性相间的排列，即limit为sp。

public class Permutation {  
  
    private static int[] s = {1,2,3,4,5,6,7,8};  
    private static int n = s.length;  
    private static int[] x = new int[n];  
      
    /** 
     * 输出集合的排列 
     * @param limit  决定选出特定条件的子集 
     * 注：all为所有排列,sp为限定元素奇偶性相间。 
     */  
    public static void all_permutation(String limit){  
        switch(limit){  
        case "all":backtrack(0);break;  
        case "sp":backtrack1(0);break;  
        }  
    }  
      
  
    /** 
     * 回溯法求集合的所有排列，依次递归 
     * 注：是否回溯的条件为精髓 
     * @param t 
     */  
    private static void backtrack(int t){  
        if(t >= n)  
            output(s);  
        else  
            for (int i = t; i < n; i++) {  //没看懂没看懂
                swap(i, t, s);  
                backtrack(t+1);  
                swap(i, t, s);  
            }  
          
    }  
  
    /** 
     * 回溯法求集合中元素奇偶性相间的排列,依次递归 
     * @param t 
     */  
    private static void backtrack1(int t){  
        if(t >= n)  
            output(s);  
        else  
            for (int i = t; i < n; i++) {  
                swap(i, t, s);  
                if(legal(x, t))  
                    backtrack1(t+1);  
                swap(i, t, s);  
            }  
          
    }  
      
    /** 
     * 对子集中元素奇偶性进行判断 
     * @param x 
     * @param t 
     * @return 
     */  
    private static boolean legal(int[] x, int t) {  
        boolean bRet = true;   //判断是否需要剪枝  
          
        //奇偶相间,即每隔一个数判断奇偶相同  
        for (int i = 0; i < t - 2; i++) {  
            bRet &= ((s[i+2] - s[i]) % 2 == 0);  
        }  
              
        return bRet;  
    }  
  
  
    /** 
     * 元素交换 
     * @param i 
     * @param j 
     */  
    private static void swap(int i, int j,int[] s) {  
        int tmp = s[i];  
        s[i] = s[j];  
        s[j] = tmp;  
    }  
      
    /** 
     * 子集输出函数 
     * @param x 
     */  
    private static void output(int[] s) {  
        for (int i = 0; i < s.length; i++) {  
                System.out.print(s[i]);  
        }  
        System.out.println();     
    }  
}

α-β剪枝算法

•一种基于剪枝（ α-βcut-off）的深度优先搜索（depth-first search）。
•将走棋方定为MAX方，因为它选择着法时总是对其子节点的评估值取极大值，即选择对自己最为有利的着法；
•将应对方定为MIN方，因为它走棋时需要对其子节点的评估值取极小值，即选择对走棋方最为不利的、最有钳制作用的着法。

•在对博弈树采取深度优先的搜索策略时，从左路分枝的叶节点倒推得到某一层MAX节点的值，可表示到此为止得以“落实”的着法最佳值，记为α。
•显然此值可作为MAX方着法指标的下界。
•在搜索此MAX节点的其它子节点，即探讨另一着法时，如果发现一个回合（2步棋）之后评估值变差，即孙节点评估值低于下界α值，则便可以剪掉此枝（以该子节点为根的子树），即不再考虑此“软着”的延伸。
•此类剪枝称为α剪枝。

•同理，由左路分枝的叶节点倒推得到某一层MIN节点的值，可表示到此为止对方着法的钳制值，记为β。
•显然此β值可作为MAX方无法实现着法指标的上界。
•在搜索该MIN节点的其它子节点，即探讨另外着法时，如果发现一个回合之后钳制局面减弱，即孙节点评估值高于上界β值，则便可以剪掉此枝，即不再考虑此“软着”的延伸。
•此类剪枝称为β剪枝。

•α-β剪枝是根据极大-极小搜索规则的进行的，虽然它没有遍历某些子树的大量节点，但它仍不失为穷尽搜索的本性。

•α-β剪枝原理中得知：
α值可作为MAX方可实现着法指标的下界
β值可作为MAX方无法实现着法指标的上界
于是由α和β可以形成一个MAX方候选着法的窗口
也便出现了各种各样的α-β窗口搜索算法。

动态规划

首先，人们认识事物的方法有三种：通过概念（即对事物的基本认识）、通过判断（即对事物的加深认识）、和推理（对事物的深层认识）。其中，推理又包含归纳法和演绎法。（这些从初中高中一直到大学我们都是一直在学习的，关键是理解）

归纳法是从特殊到一般，属于发散思维；（如：苏格拉底会死；张三会死；李四会死；王五会死……，他们都是人。所以，人都会死。）

演绎法是从一般到特殊，属于汇聚思维。（如：人都会死的；苏格拉底是人。所以，苏格拉底会死。）

那么，如何用归纳法解决数学问题，进行应用呢？

已知问题规模为n的前提A，求解一个未知解B。（我们用An表示“问题规模为n的已知条件”）

此时，如果把问题规模降到0，即已知A0，可以得到A0->B.

如果从A0添加一个元素，得到A1的变化过程。即A0->A1; 进而有A1->A2; A2->A3; …… ; Ai->Ai+1. 这就是严格的归纳推理，也就是我们经常使用的数学归纳法；
对于Ai+1，只需要它的上一个状态Ai即可完成整个推理过程（而不需要更前序的状态）。我们将这一模型称为马尔科夫模型。对应的推理过程叫做“贪心法”。

然而，Ai与Ai+1往往不是互为充要条件，随着i的增加，有价值的前提信息越来越少，我们无法仅仅通过上一个状态得到下一个状态，因此可以采用如下方案：

{A1->A2}; {A1, A2->A3}; {A1,A2,A3->A4};……; {A1,A2,...,Ai}->Ai+1. 这种方式就是第二数学归纳法。
对于Ai+1需要前面的所有前序状态才能完成推理过程。我们将这一模型称为高阶马尔科夫模型。对应的推理过程叫做“动态规划法”。

上述两种状态转移图如下图所示：

下面通过分析几个经典问题来理解动态规划。

实例一：最长递增子序列（Longest Increasing Subsequence）。

问题描述。给定长度为N的数组A，计算A的最长单调递增的子序列（不一定连续）。如给定数组A{5，6，7，1，2，8}，则A的LIS为{5，6，7，8}，长度为4.

思路：因为子序列要求是递增的，所以重点是子序列的起始字符和结尾字符，因此我们可以利用结尾字符。想到：以A[0]结尾的最长递增子序列有多长？以A[1]结尾的最长递增子序列有多长？……以A[n-1]结尾的最长递增子序列有多长？分析如下图所示：

（动态规划solution）所以我们可以使用一个额外的空间来保存前面已经算得的最长递增子序列，然后每次更新当前的即可。也就是问题演化成：已经计算得到了b[0,1,2,……,i-1]，如何计算得到b[i]呢？

显然，如果ai>=aj，则可以将ai放到b[j]的后面，得到比b[j]更长的子序列。从而：b[i] = max{b[j]}+1. s.t. A[i] > A[j] && 0 <= j < i.

所以计算b[i]的过程是，遍历b[i]之前的所有位置j，找出满足关系式的最大的b[j].

得到b[0...n-1]之后，遍历所有的b[i]找到最大值，即为最大递增子序列。总的时间复杂度为O(N2).

我实现的Java版代码为：

publi int LIS(int[] A) {
        if(A == null || A.length == 0)
            return 0;
        int[] b = new int[A.length];
        b[0] = 1;
        int result = 1;
        for(int i=1; i<A.length; i++) {
            int max = -1;
            for(int j=0; j<i; j++) {
                if(A[j] < A[i] && b[j] > max)
                    max = b[j];
            }
            b[i] = max + 1;
            result = Math.max(result, b[i]);
        }
        return result;
    }

进而，如果不仅是求LIS的长度，而要求LIS本身呢？我们可以通过记录前驱的方式，从该位置找到其前驱，进而找到前驱的前驱……

Java代码如下：

public static ArrayList<Integer> LISDetail(int[] A) {
        if(A == null || A.length == 0)
            return null;
        int[] b = new int[A.length];
        int[] b1 = new int[A.length];
        b[0] = 1;
        b1[0] = -1;
        int result = 1;
        int index = 0;
        for(int i=1; i<A.length; i++) {
            int max = 0;
            boolean flag = false;
            for(int j=0; j<i; j++) {
                if(A[j] < A[i] && b[j] > max) {
                    flag = true;
                    max = b[j];
                    b1[i] = j;
                }
            }
            if(flag == false) b1[i] = -1;
            b[i] = max + 1;
            if(result < b[i]) {
                result = b[i];
                index = i;
            }
        }
        ArrayList<Integer> res = new ArrayList<Integer>();
        //res.add(A[index]);
        for(;index >=0; ) {
            res.add(A[index]);
            index = b1[index];
        }
        Collections.reverse(res);
        return res;
    }

使用动态规划方法的到O(N2)的时间复杂度算法，能否有更优的方法呢？

（贪心算法solution）我们仍然使用上面的例子，用其他的思路试试。我们递增式的选择元素，让每一次的选择尽可能的小，实际操作如下：

最开始，缓冲区里为空；

看到了字符“1”，添加到缓冲区的最后，即缓冲区中是“1”；

看到了字符“4”，“4”比缓冲区的所有字符都大，因此将“4”添加到缓冲区的最后，得到“14”；

看到了字符“6”，“6”比缓冲区的所有字符都大，因此将“6”添加到缓冲区的最后，得到“146”；

看到了字符“2”，“2”比“1”大，比“4”小，因此将“4”直接替换成“2”，得到“126”；

看到了字符“8”，“8”比缓冲区的所有字符都大，因此将“8”添加到缓冲区的最后，得到“1268”；

看到了字符“9”，“9”比缓冲区的所有字符都大，因此将“9”添加到缓冲区的最后，得到“12689”；

看到了字符“7”，“7”比“6”大，比“8”小，因此将“8”直接替换成“7”，得到“12679”；

现在，缓冲区的字符数目为5，因此，数组A的LIS的长度就是5！

这样，时间复杂度变为每次都在一个递增的序列中替换或插入一个新的元素，所以为O(nlogn)。

代码为：

public int len = 0;
    public int LIS1(int[] A) {
        if(A == null || A.length == 0)
            return 0;
        int[] b = new int[A.length];
        b[0] = A[0];
        len = 1;
        for(int i=1; i<A.length; i++) {
            insert(b, A[i]);
        }
        return len;
    }
    
    
    public int[] insert(int[] a, int val) {
        if(val < a[0]) {
            a[0] = val;
            return a;
        }
        if(val > a[len-1]) {
            a[len] = val;
            len++;
            return a;
        }
        int left = 0, right = len-1, mid = (left + right) / 2;
        while(left < right) {
            mid = (left + right) / 2;
            if(a[mid] < val && a[mid+1] >= val) {
                a[mid+1] = val;
                return a;
            }
            if(a[mid] >= val && a[mid-1] < val) {
                a[mid] = val;
                return a;
            }
            if(a[mid] < val) 
                left = mid+1;
            if(a[mid] > val)
                right = mid-1;
        }
        return a;
    }

但后来我分析了这种方法只能得到长度，不能得到子序列本身。（老师上课时提示说考虑序列长度变化的时候，对于示例数组{1，4，6，2，8，9，7}来说可以解决，即当序列变长的时候，元素1，4，6，8，9正好是最终的字长递增子序列；当如果原数组是{10，9，2，5，3，7，101，18}时，就不是这么回事了。目前我没有找到求解子序列本身的方法，留作以后思考。）

实例二：格子取数/走棋盘问题

问题描述。给定一个m*n的矩阵，每个位置是一个非负整数，从左上角开始放一个机器人，它每次只能朝右和下走，走到右下角，求机器人的所有路径中，总和最小的那条路径。如下图所示，其中图中所示的彩色方块是已知的某些非负整数值。

考虑一般情况下位于机器人位于某点(x, y)处，那么它是怎么来的呢？只可能来自于左边或者上边。即：

dp[x, y] = min(dp[x-1, y], dp[x, y-1]) + a[x, y],其中a[x, y]是棋盘中(x, y)点的权重取值。

然后考虑位于最左边一列与左上边的一行，得到所有的状态转移方程为：

所以代码如下：

public int minPath(int[][] chess) {
        int row = chess.length;
        int col = chess[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = chess[0][0];
        for(int i=1; i<row; i++) 
            dp[i][0] = dp[i-1][0] + chess[i][0];
        for(int j=1; j<col; j++)
            dp[0][j] = dp[0][j-1] + chess[0][j];
        for(int i=1; i<row; i++) {
            for(int j=1; j<col; j++) {
                dp[i][j] = (dp[i-1][j] < dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]) + chess[i][j];
            }
        }
        return dp[row-1][col-1];
    }

观察状态转移方程发现，每次更新(x, y)，只需要最多知道上一行即可，没必要知道更早的数据。凡是满足这样条件的动态规划问题，都可以用“滚动数组”的方式做空间上的优化。

使用滚动数组的状态转移方程如上图所示。

代码如下：

public int minPath1(int[][] chess) {
        int row = chess.length;
        int col = chess[0].length;
        int[] dp = new int[col];
        dp[0] = chess[0][0];
        for(int j=1; j<col; j++)
            dp[j] = dp[j-1] + chess[0][j];
        for(int i=1; i<row; i++) {
            for(int j=0; j<col; j++) {
                if(j == 0)
                    dp[j] += chess[i][j];
                else
                    dp[j] = (dp[j] < dp[j-1] ? dp[j] : dp[j-1]) + chess[i][j];
            }
        }
        return dp[col-1];
    }

实例三：找零钱问题/0-1背包问题

问题描述。给定某不超过100万元的现金总额，兑换成数量不限的100、50、20、10、5、2、1元的纸币组合，共有多少种组合？

思路：此问题涉及两个类别：面值和总额。所以我们定义dp[i][j]表示使用小于等于i的纸币，凑成j元钱，共有多少种组合方法。比如dp[100][500]表示使用面值不大于100的纸币，凑出500块钱，共有多少种组合方法。

进一步思考，如果面值都是1元的，则无论总额多少，可行的组合数都为1.比如只用1元的纸币凑出100元，显然只有一种组合方法。那么如果多出一种面值呢？组合数有什么变化？

回到dp[100][500]，既然用小于等于100的纸币凑出500块钱，则组合中只会要么包含至少一张100块的纸币，要么不包含100块的纸币。所以我们可以分成两种情况考虑：

1）如果没有包括100元，则用到的最大面值可能为50元，即使用面值小于等于50的纸币，凑出500块钱，表示形式为：dp[50][500];

2）如果必须包含100元，怎么计算呢？既然至少包含100元，我们先拿出100块钱，则还需要凑出400块钱即可完成。用小于或等于100元的纸币凑出400块钱，表示形式为dp[100][400];

将两者综合起来为：dp[100][500] = dp[50][500] + dp[100][400];

为了方便表示，我们定义纸币面值为一个数组：dom[] = {1,2,5,10,20,50,100},这样dom[i]和dom[i-1]就表示相邻的纸币面额了。i的意义从面值变成了面值下标。

根据上面分析，对于一般情况，我们有dp[i][j] = dp[i-1][j] + dp[i][j-dom[i]]. ]有了一般情况，在考虑两种特殊情况：

如果dp[i][0]应该返回啥？dp[i][0]表示用小于等于i的纸币，凑出0块钱，我们可以定义这种情况的值为1；

如果dp[0][j]应该返回啥？dp[0][j]表示用小于等于0的纸币，凑出j块钱，我们可以定义这种情况的值为1.

再看dp[100][78]，用小于等于100元的纸币凑出78块钱，这时组合中一定不会包含100块的纸币，因此dp[100][78] = dp[50][78],即当j < dom[i]时，dp[i][j] = dp[i-1][j]。

这样整个dp的过程就出来了：

public int charge(int[] money, int total) {
        int row = money.length;
        int col = total + 1;
        int[][] dp = new int[row][col];
        for(int j=0; j<col; j++)
            dp[0][j] = 1; //表示用1块钱凑出任何金额的组合数都为1
        for(int i=1; i<row; i++) {
            dp[i][0] = 1; 
            for(int j=1; j<col; j++) {
                if(j < money[i])  //表示要凑出的金额数小于当前的纸币面额，如dp[100][87] = dp[50][87]
                    dp[i][j] = dp[i-1][j];
                else 
                    dp[i][j] = dp[i-1][j] + dp[i][j-money[i]];
            }
        }
        return dp[row-1][col-1];
    }

总结，什么时候适合用动态规划呢？

总之，动态规划只是一种解决问题的思路，要灵活运用这种方法，多做练习，就能很快找到灵感了。

常用算法（二）