数据结构学习笔记——第一章：绪论（下）

五、动态规划

5.1 什么是动态规划

  所谓动态规划，可以理解为先通过递归找出算法的本质，并给出一个初步的解之后，再将其转化为等效的迭代的形式。

• 根据fib数列的定义，我们可以直接写出最naive的形式：

int fib(int n){
    return n<2 ?
        n : fib(n-1) + fib(n-2);
}

• 但是上面的代码时间复杂度为
  

  Fig. 1. 递归版本的fib数列存在大量重复调用的实例

• 然而实际上每个实例只需要被调用一次就够了，如上右图。

• 扩展：值得注意的是，另一个常见的问题——上台阶问题，可以等效为斐波那契数列：上一个楼梯，每次可以上一个台阶或者两个台阶。现给定台阶数目，问上到这一台阶可以有几种走法。考虑上到最后台阶是通过一步(f(1)=1)还是两步(f(2)=2)，可以发现该问题实际是一个fib数列。

5.2 最长公共子序列(LCS)问题

Fig. 2 LCS示意

5.2.1 求解：

• 对于长度分别为m, n的两序列A、B的LCS问题，可以利用“减而治之”的方法，按照如下思路分析：
   1. 考虑平凡的情况：若A、B中有一个为空字符串，则LCS为空串；
   2. 从右往左分析：假如A、B的最后一个字符相同，则可以对A、B同时去除末尾字符，然后对剩下的前缀求LCS，全局LCS即前缀的LCS+末字符。
   3. 假如A、B最后一个字符不同，则A、B的末字符中一定有一个对LCS没有贡献（仔细思考下便知）。故可以去除A的末字符，然后求LCS(A[0:m), B[0:n])；或者对称的，去除B的末字符，然后求LCS(A[0:m], B[0:n))；然后只需要求出这两种情况下解中最长的那个即可。

• 这样就构成了一个完整的算法：第一步描述了算法的递归基，后两步为递归的内容。

//string lcs(string &A, string &B){
//error: invalid initialization of non-const reference of type ‘std::__cxx11::string& {aka std::__cxx11::basic_string<char>&}’ from an rvalue of type ‘std::__cxx11::basic_string<char>’
//         return lcs(A.substr(0, m), B.substr(0, n)) + A[m];
//         A.substr(0,m)为临时变量, c++中临时变量不能作为非const的引用参数, 因为修改一个临时变量是无意义的。
//         https://blog.csdn.net/kongying168/article/details/3864756
//
string lcs(string A, string B){
    int m = A.size()-1;
    int n = B.size()-1;
    if (m==-1 | n==-1){
        return string();
    }
    if (A[m]==B[n]){
        return lcs(A.substr(0, m), B.substr(0, n)) + A[m];
    }
    else{
        string lcsL = lcs(A.substr(0, m), B);
        string lcsR = lcs(A, B.substr(0, n));
        return
            lcsL.size() > lcsR.size() ? lcsL : lcsR;
    }
}

• 注意上面代码中将开区间转换为闭区间处理。

  
  Fig. 3 正确性分析

5.5.2 性能分析

Fig. 4. 大量重复唤醒的实例极大提高了开销

• 如上图所示，如考虑最坏的情况，则中间某一个状态(a,b)被唤醒的次数可以看做是从右下角出发到达该点的所有合法路径的总数（即所有水平路径/竖直路径的总数）。经过粗略分析可知，该解法的复杂度为指数复杂度。