动态规划心得

什么是动态规划

动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

动态规划两个最重要的特征就是：最优子结构和重叠子问题（与分治法的区别）。

最优子结构

用动态规划求解优化问题的第一步是描述最优解的结构。如果一个问题的最优解中蕴含了子问题的最优解，即该问题具有最优子结构，这是是用动态规划的前提条件。当然，此时也可能会用贪心策略。

如何寻找问题的最优解与子问题的最优解之间的递推关系（或者叫状态转移方程），是解决动态规划问题最重要的一步。那么如何找到递推关系呢？我们需要考虑两个问题：

1．有多少个子问题被使用在一个原问题的最优解中？

2．在决定最优解使用那个子问题时有多少个选择？

这两个问题搞明白了，那么动态规划问题也就迎刃而解了。当然，这也是最难的部分，需要具体问题具体分析。在这里给出一些技巧：

a．如何选取解空间维度：

对于两个序列的问题，显然要用二维表示c[i][j]，比如求最长公共子序列、两个字符串的编辑距离。此时一般要考虑c[i][j]与c[i-1][j],c[i][j-1],c[i-1][j-1]的关系；

对于一个序列的问题，如果最优解是通过选择两个子问题的解并将其结合起来而得到的，就用二维表示，比如矩阵连乘法、整齐打印。此时要考虑c[i][j]与c[i][k]、c[k+1][j]（或者是c[i][k-1],x[k],c[k+1][j]）的关系。注意，对于这种情况，两个子问题之间必须是独立的，他们没有重叠的子子问题；

对于一个序列的问题，如果最优解是通过选择一个子问题的解并经过某种操作而得到，那就用一维表示c[i]，比如装配线调度、最长单增序列。此时要考虑c[n]与c[k]的关系；

对于树结构，一般都是考虑与子树的关系，比如最有二叉查找树、公司聚会问题。

重叠子结构

适用于动态规划求解的最优化问题必须具有的第二个要素就是重叠子问题。也就是说用来解原问题的递归算法产生的问题许多都是同样的子问题，而适合用分治法解决的问题往往在递归的每一步都产生全新的问题。这样以来，每个子问题只解一次，把解保存在一个表中，需要时即可查看，就不用重新计算了。

所以，动态规划在形式上往往表现为填矩阵的形式。先计算出初始值，然后自底向上（依赖于递推式的形式）填表，知道找出最优解。还有一点要注意的是，填表的次序也决定了能否优化空间复杂度。

做备忘录

动态规划相对于递归的优势是重叠子结构，而递归相对于动态规划的优势是避免了对不必要子问题的求解。把递归和动态规划结合起来，就得到一种做备忘录的方法，它比普通的递归算法多了一个可以查询的表。当然，它比动态规划也多了递归的代价。

1．给备忘录赋初值，如m[i][j]=-1；

2．递归，每次找到一个值q<m[i][j]且m[i][j]!=-1，就让m[i][j]=q。

算法时间复杂度

动态规划算法的时间复杂度等于子问题的个数乘以需要做的选择的个数。比如任务调度问题中，子问题个数为n，每一步的选择数为2，故时间复杂度为O(n)；而在矩阵连乘法中，子问题的个数为n*n，每一步所做的选择数为n，故时间复杂度为n*n*n。

至此，动态规划理论基础就讲完了，下面看一个例子。

例1：请给出一个O(n*n)时间的算法，使之能找出一个n个数的序列中最长的单调递增子序列。

先给出一个序列1，3，4，2，1，3，9，2，6。

不考虑时间复杂度的情况下：

第一步，先找出递推关系式。

a．首先，我们选取解空间的维度。对于一个序列的问题，如果选择二维的，用s[1][n]表示n个数的最长单增子序列，那么s[i][j]可有s[i][k]与s[k+1][j]（或者是s[i][k-1],x[k],s[k+1][j]）结合得到。其中有一个条件，s[i][k]中的最大值必须小于s[k+1][j]中的最小值，要满足这个条件，s[i][k]就可能不是x[i]-x[k]序列的最优解，故二维表示法不可行。

b．当然，一般我们会先考虑一维的情况。用s[n]表示n个数的序列中的最长单增子序列，我们第一个想到的必然是s[n]如何由s[n-1]得到，通过分析，s[n]不仅与x[1]-x[n-1]中的最长子序列有关，还与x[1]-x[n-1]中的其他子序列有关，这取决于子序列中的最大值。

显然，s[n]=(1<=k<n) max {s[k]+1,如果s[k]中的最大值<x[n];

s[k], 如果s[k]中的最大值>=x[n];}

初始值s[1]=1。同时我们还需要一个数组m[n]来记录s[n]中的最大值。

还有另一种表示解的方法。用c[k]表示以x[k]结束的最长单增子序列的长度，那么

c[n]=(c<=k<n) max { c[k]+1,x[k]<x[n],n>1;

1 ,x[k]>=x[n],n>1;

1 ,n=1}

在考虑时间复杂度的情况下：

虽然放在后面，但这才是解题的正确思路（利用题目给出的所有条件）。

在一维表示中，子问题的个数是n，时间复杂度为O(n*n)，故需要做的选择个数为n，故s[n]与s[k]有关(1<=k<n)。

当时间复杂度变为O(nlogn)时，子问题的个数是n，故需要做的选择个数为logn，对于这个值，我们最先想到的是二分法。这里要用到一个思想：在x[1]-x[i]中的所有子序列中，长度相同的我们只需保留最大值最小的那个子序列。我们用一个新数组max[i]表示长度为i的子序列中的最小的最大值。每输入一个数，就用二分法查找其在max[i]中的位置，然后决定是否改变max[i]的值，或增加一个max[i+1]的值。

时间复杂度为O(n*n)的代码：

typedef struct {
    int length;
    int prev;
} state;

//算法核心
state *a = malloc(sizeof(state) * n);
for(i=0;i<n;i++) {
    a[i].length = 1;
    a[i].prev = -1;
}

for(i=1;i<n;i++)
    for(j=1;j<i;j++)
        if(array[i]>array[j] && a[i].length < a[j].length + 1)
        {
            a[i].length = a[j].length + 1;
            a[i].prev = j;
            if(a[i].length > max_length) {
                max_length = a[i].length;
                max_end = i;
            }
        }

时间复杂度为O(n*logn)的代码：

int lis_ologn(int *array, int length) {
    int i, left,right,mid,max_len = 1;
    int *MaxV;
    if(!array)
        return 0;
    MaxV = (int*)malloc(sizeof(int)*(length+1));
    MaxV[0] = -1;
    MaxV[1] = array[0];

    for(i=1;i<length;i++){
        //寻找范围是MaxV[1, ... , max_len]
        left = 1;
        right = max_len;
        //二分查找MaxV中第一个大于array[i]的元素
        while(left<right) {
            mid = (left+right)/2;
            if(MaxV[mid]<=array[i])
                left = mid + 1;
            else if(MaxV[mid]>array[i])
                right = mid;
        }
        if((MaxV[right]>array[i])&&(MaxV[right-1]<array[i]))
            MaxV[right] = array[i];
        else if (MaxV[right]<array[i]) {
            MaxV[right+1] = array[i];
            max_len++;
        }
    }
    return max_len;
}

参考文献：1.算法导论

2.http://www.cnblogs.com/wuyuegb2312/p/3281264.html#q4

3.http://blog.csdn.net/mengzhejin/article/details/37880413

4.http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741374.html

秒客网