算法导论学习笔记（六）：动态规划

转载请注明原作者 @yoshino，强烈要求简书支持TOC目录和数学公式的输入！
更新不及时，有空慢慢写吧，原文是写在Bear上粘贴来简书的，可能格式有点乱。
具体的工程在我的github上。

---

动态规划（dynamic programming,DP），与分治策略相似，通过求解子问题来求解原问题，不同于分治策略的事DP的子问题是相互重叠的，DP通常是用来求解最优化问题，设计一个动态规划算法步骤：

1. 刻画一个最优解的结构特征
2. 递归地定义最优解的值
3. 计算最优解的值，通常采用自底向上的方法
4. 利用计算出的信息构造一个最优解

钢条切割

钢条切割问题描述

求解思路

对于一根程度为l的钢条，有两种不同的切割法：

• 不切割：此时的收益为r_l=p_l
• 切割成长度i和l-i两部分：此时收益用递归表示：r_l=r_i+_l-i
  最大收益可以写成：p=max(p_l,r_i+_l-i,…,r₁+_l-1)
  即取其中最大的

两种动态规划算法：

• 带备忘的自顶向下算法：按照自然递归的形式编写过程，过程中保留之前子问题的解，其中会检查是否已经保过此解，如果已经保存了就直接返回保存的值，从而节省了计算的时间。

    public int memoizedCutRodAux(int price[], int r[], int l) {//带备忘的自顶向下法
        if (r[l] > 0) {
            return r[l];//r[l]用来存储当长度为l时的最优解,price用来存储题目给出的收益值
        } else {
            int profit = 0;
            for (int i = 1; i <= l; i++) {
                profit=Math.max(profit,price[i]+memoizedCutRodAux(price,r,l-i));
            }
            r[l]=profit;//保存最优解
            return profit;
        }
    }

• 自底向上法：任何子问题的求解都依赖于更小子问题的求解，把子问题按照规模大小进行排序，按从大到小的顺序进行求解，这样求解时保证每个求解的问题的前提子问题都已经求解过了

public int bottomUpCutRod(int price[], int r[], int l) {
        for (int i = 1; i <= l; i++) {
            int profit = 0;
            for (int j = 1; j <= i; j++) {
                profit = Math.max(profit, price[j] + r[i - j]);
            }
            r[i] = profit;
        }
        return r[l];
    }

最长公共子序列（longest-common-subsequence,LCS）

问题描述

给定两个公共子序列X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>，求X Y的长度最长的公共子序列，子序列不要求要连续，但是顺序要相同

问题分析

1. 刻画LCS特征，定义前缀对：

   
   前缀对
   

   从定理15.1可以得出，两个序列的LCS包含两个序列的前缀的LCS。

2. 得出一个递归解
   从定理15.1可以知道：

• 若x_m=y_n，则求解X_m-1和Y_n-1的LCS，将x_m=y_n至于后面即可
• 若x_m不等于y_n，则求解X_m-1和Y_n的LCS和X_m和Y_n-1的LCS，取其中较长的作为LCS
  之所以能做这样的假设，是因为最优解必然出现在X和Y中。
  LCS递归公式

3. 计算LCS的长度

• 建立一个矩阵c[0...m,0...n]用来保存c[i,j]的值
• 建立一个表b[1...m,1...n]用来保存最优解，即b[i,j]保存c[i,j]的子问题最优解
• java代码实现

private int[][] LCSLength(String[] X, String[] Y) {
        ArrayList<ArrayList> result = new ArrayList<ArrayList>();
        int m = X.length;
        int n = Y.length;
        int[][] c = new int[m + 1][n + 1];
        int[][] b = new int[m + 1][n + 1];
        for (int i = 1; i < m; i++)
            for (int j = 0; j < n + 1; j++) {
                c[i][j] = 0;
            }
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) {
                if (X[i - 1] == Y[j - 1]) {//为了照顾c的序号，所以所有的X,Y均-1了
                    c[i][j] = c[i - 1][j - 1] + 1;
                    b[i][j] = 1;//代表左上箭头
                } else if (c[i - 1][j] >= c[i][j - 1]) {
                    c[i][j] = c[i - 1][j];
                    b[i][j] = 2;//代表向上箭头
                } else {
                    c[i][j] = c[i][j - 1];
                    b[i][j] = 3;//代表向左箭头
                }
            }
        return b;
    }

4. 构造LCS
   从第三步我们得到的b[i,j]，我们得到了构造LCS的方向，递归回溯打印LCS即可

    private void printLCS(int[][] b, String[] X, int i, int j) {
        if (i != 0 && j != 0) {
            if (b[i][j] == 1) {
                printLCS(b, X, i - 1, j - 1);
                System.out.print(X[i-1]);
            } else if (b[i][j] == 2) {
                printLCS(b, X, i - 1, j);
            } else {
                printLCS(b, X, i, j - 1);
            }
        }
    }

最优二叉搜索树

问题描述

给定一个n个不同关键字的已排序的序列K=<k1,k2,...,kn>(递增序列)，对于每个关键字ki,都有一个概率pi表示其搜索频率。当然有些搜索的值可能不在K中，所以我们给出n+1个伪关键字“d0,d1,…,dn”,其中d0表示所有小于k1的值，dn表示所有大于kn的值，对于每个di，也有相应的概率pi