动态规划法

前面讲述了分治法，分治法是把问题分解成一个个小问题，再把小问题的解合并成原问题的解。这里有个前提就是小问题之间是相互独立的，并没有相互影响，比如用分治法求解最大子段问题，一分为二的子段的最大子段和并不相互影响。那如果遇到相互影响的问题呢？动态规划法就是解决这类问题的。
来看0-1背包问题。
问题描述：有n个物品，第i个物品价值为Vi，重量为Wi，其中Vi和Wi均为非负数，背包的容量为W，W为非负数。现需要考虑如何选择装入背包的物品，使装入背包的物品总价值最大。
该问题可以形式化描述如下:
* 目标函数为max∑ViXi(i=1,2,3...n,Xi∈{0,1})
* 约束条件为∑WiXi≤W(i=1,2,3...n,Xi∈{0,1})
* 满足约束条件的任一集合（X1,X2,X3,...,Xn）是问题的一个可行解，问题的目标是要求问题的一个最优解。
解决思路：
* 如果最优解包含第n个物品，即Xn=1，那么其余X1，X2，...，Xn-1一定构成子问题1,2，...，n-1在容量W-Wn时的最优解。
* 如果最优解不包含第n个物品，即Xn=0，那么其余X1，X2，...，Xn-1一定构成子问题1,2，...，n-1在容量W时的最优解。
* 根据以上分析的最优解的结构递归地定义问题最优解。
* 设C[i][w]表示背包容量为w时i个物品导致的最优解的总价值，得到下面的表达式。问题是要求C[n][W].
* i=0或w=0时，C[i][w]=0；
* i>0且Wi>w时，C[i][w]=C[i-1][w]；
* i>0且Wi≤w时，C[i][w]=max{C[i-1][w-Wi]+Vi,C[i-1][w]}；
java代码：

    public static void zeroOne(int[] V,int[] W,int tW,int n){
        //总价值二维数组
        int[][] C = new int[n+1][tW+1];
        for(int i=1; i<= n; i++){
            for(int j=1; j<= tW; j++){
                C[i][j] = W[i-1] > j ? C[i-1][j] : Math.max(C[i-1][j-W[i-1]] + V[i-1], C[i-1][j]);
            }
        }
        printIntTwoArray(C);
        int maxValue = C[n][tW] > C[n-1][tW] ? C[n][tW] : C[n-1][tW];
        System.out.println("背包所装物品的最大价值是：" + maxValue);
        //获取0-1序列
        int[] x = new int[n];
        int weight = tW;
        for(int i = n; i>=1; i--){
            if(C[i-1][weight] == C[i][weight]){
                x[i-1] = 0;
            }else{
                x[i-1] = 1;
                weight -= W[i-1];
            }
        }
        printIntOneArray(x);
    }
    
    static void printIntOneArray(int[] array){
        int length = array.length;
        if(length < 1){
            return;
        }
        for(int i=0;i<length;i++){
            System.out.print(array[i]+"\t");
        }
    }
    
    static void printIntTwoArray(int[][] array){
        int row = array.length;
        if(row < 1){
            return;
        }
        int column = array[row-1].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<column;j++){
                System.out.print(array[i][j]+"\t");
            }
            System.out.println();
        }
    }

再举个例子，最长公共子序列（LCS）问题。
如两个序列，X=A,C,B,D,A和Y=C,A,F,D,A的最长公共序列是C,D,A（不一定是连续的子序列）
设X=X1,X2,...,Xm，Y=Y1,Y2,...,Yn这两个序列
最终的最长公共子序列是Z=Z1,Z2,...,Zk,用L(m,n)表示最后一个元素是Xm的序列X和最后一个元素是Yn的序列Y的最长公共子序列的长度
* ㈠若Xm=Yn，那么Zk=Xm=Yn，则L(m,n)=L(m-1,n-1)+1
* ㈡若Xm≠Yn，则L(m,n)=max{L(m-1,n),L(m,n-1)}
java代码：

    static void LCS(char[] X,char[] Y){
        int m = X.length;
        int n = Y.length;
        int[][] L = new int[m+1][n+1];
        for(int i = 1; i <= m;i++){
            for(int j = 1; j <= n;j++){
                L[i][j]= X[i-1]==Y[j-1] ? L[i-1][j-1]+1 : Math.max(L[i-1][j], L[i][j-1]);
            }
        }
        printIntTwoArray(L);
        char[] Z = new char[L[m][n]];
        int num = 0;
        int i = m;
        int j = n;
//      while(i>0&&j>0){
//          if(L[i][j]!=L[i-1][j]){
//              Z[num++] = X[i-1];
//              i--;
//              j--;
//              while(j>0&&L[i][j]==L[i][j-1]){
//                  j--;
//              }
//          }else{
//              i--;
//          }
//      }
        while(i>0&&j>0){
            if(L[i][j]!=L[i][j-1]){
                Z[num++] = Y[j-1];
                i--;
                j--;
                while(i>0&&L[i][j]==L[i-1][j]){
                    i--;
                }
            }else{
                j--;
            }
        }
        System.out.print("最长公共子序列：");
        printIntOneArray(Z,false);
        System.out.println("最长公共子序列的长度："+L[m][n]);
    }
    static void printIntOneArray(char[] array,boolean isAsc){
        int length = array.length;
        if(length < 1){
            return;
        }
        if(isAsc){
            for(int i=0;i<length;i++){
                System.out.print(array[i]+"\t");
            }
        }else{
            for(int i=length-1;i> -1;i--){
                System.out.print(array[i]+"\t");
            }
        }
    }