动态规划习题总结

1、最长公共子串Longest-Common-Substring：有两个字符串，求这两个字符串的最长公共子串，要求子串是连续的

/ 最长公共子串 DP
int dp[100][100];
void LCS_dp(char * X, char * Y) 
{
    int xlen = strlen(X);
    int ylen = strlen(Y);
    int maxlen = 0;
    int maxindex = 0;     
    for(int i = 0; i < xlen; ++i)
    {
        for(int j = 0; j < ylen; ++j)
        {
            if(X[i] == Y[j])
            {
                if(i && j)
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                if(i == 0 || j == 0)
                {
                    dp[i][j] = 1;
                }
                if(dp[i][j] > maxlen)
                {
                    maxlen = dp[i][j];
                    maxindex = i + 1 - maxlen;
                }
            }
        }
    }
    if(maxlen == 0)
    {
        printf("NULL LCS\n");
        return;
    }
    printf("The len of LCS is %d\n",maxlen);
    int i = maxindex;
    while(maxlen--)
    {
        printf("%c",X[i++]);
    }
    printf("\n"); 
}

dp[i][j]，表示A串中以A[0,i],以i为尾和B串中以B[0,j]中以j为尾的两个子字符串中最长子串的长度（注意这个子串在两个主串中，必须以i，j为尾）

初始化：i==0||j==0时，此时可以直接判断X[i]==X[j]，表示的意义是，为0为尾的字符串，和以j为尾的字符串，是否相等（此时就一个数值）　

故状态转移方程

X[i] == Y[j]，dp[i][j] = dp[i-1][j-1] + 1
X[i] != Y[j]，dp[i][j] = 0

2. 最长公共子序列

分析过程：

通常的算法就是动态规划(DP)。假设现在有两个字符串序列：X={x1,x2,...xi...xm},Y={y1,y2,...yj...yn}。如果我们知道了X={x1,x2,...xi-1}和Y={y1,y2,...yj-1}的最大公共子序列L，那么接下来我们可以按递推的方法进行求解：

1)如果xi==yj,那么{L,xi(或yj)}就是新的LCS了，其长度也是len(L)+1。这个好理解，即序列{Xi,Yj}的最优解是由{Xi-1,Yj-1}求得的。

2)如果xiyj,那么可以转换为求两种情况下的LCS。

A: X={x1,x2,...xi}与Y={y1,y2,...yj-1}的LCS，假设为L1

B: X={x1,x2,...xi-1}与Y={y1,y2,...yj}的LCS，假设为L2

那么xiyj时的LCS=max{L1,L2},即取最大值。同样，实际上序列{Xi,Yj-1}和{Xi-1,Yj}都可以由{Xi-1,Yj-1}的最优解求得。

怎么样，是不是觉得这种方法很熟悉？当前问题的最优解总是包含了一个同样具有最优解的子问题，这就是典型的DP求解方法。好了，直接给出上面文字描述解法中求LCS长度的公式：

注意：此dp[i][j]是从i=0，j=0开始的，但是并不对应数组X[i],Y[j]，主要是为了边界条件的方便，dp[1][1]才对应数组的首元素X[0],Y[0]（关键点）

这里用一个二维数组存储LCS的长度信息，i，j分别表示两个字符串序列的下标值。这是求最大公共子序列长度的方法，如果要打印出最大公共子序列怎么办？我们还需要另外一个二维数组来保存求解过程中的路径信息，方便最后进行路径回溯，找到LCS。如果看着很含糊，我下面给出其实现过程。

flow

二：DP实现

很多博文上面都有，基本上是用两个二维数组c[m][n]和b[m][n]，一个用来存储子字符串的LCS长度，一个用来存储路径方向，然后回溯。

其中二维数组b[i][j]的取值为1或2或3，其中取值为1时说明此时xi=yj，c[i][j]=c[i-1][j-1]+1。如果将二维数组看成一个矩阵，那么此时代表了一个从左上角到右下角的路径。如果取值为2，说明xi≠yj,且c[i][j]=c[i-1][j]，代表了一个从上到下的路径，同理取值为3代表一个从左到右的路径。

最后我们可以根据c[m][n]的值知道最大公共子序列的长度。然后根据b[i][j]回溯，可以打印一条LCS。其中b[i][j]=1的坐标点对应的字符同时在两个序列中出现，所以依次回溯这个二维数组就可以找到LCS了。这里给出实现代码：

复制代码
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #include "stack.h"
 5 #define MAX_LEN 1024
 6 typedef int **Matrix;
 7 
 8 void GetLCSLen(char *str1, char *str2, Matrix pc, Matrix pb, int nrow, int ncolumn);
 9 Matrix GreateMatrix(int nrow, int ncolumn);
10 void DeleteMatrix(Matrix p, int nrow, int ncolumn);
11 void TraceBack(char *str1, Matrix pb, int nrow, int ncolumn);
12 
13 void GetLCSLen(char *str1, char *str2, Matrix pc, Matrix pb, int nrow, int ncolumn)
14 {
15     int i,j;
16     /************initial the edge***************/
17     for(i=0; i<nrow; i++)
18     {
19         pc[i][0] = 0;
20         pb[i][0] = 0;
21     }
22     for(j=0; j<ncolumn; j++)
23     {
24         pc[0][j] = 0;
25         pb[0][j] = 0;
26     }
27     /************DP*****************************/
28     for(i=1; i<nrow; i++)
29     {
30         for(j=1; j<ncolumn; j++)
31         {
32             if(str1[i-1] == str2[j-1])
33             {
34                 pc[i][j] = pc[i-1][j-1] + 1;//由左上节点转移而来
35                 pb[i][j] = 1;//标记为1
36             }
37             else if(pc[i-1][j] >= pc[i][j-1])
38             {
39                 pc[i][j] = pc[i-1][j];//由上节点转移而来
40                 pb[i][j] = 2;//标记为2
41             }
42             else
43             {
44                 pc[i][j] = pc[i][j-1];//由左节点转移而来
45                 pb[i][j] = 3;//标记为2
46             }
47         }
48     }
49 }
50 void TraceBack(char *str1, Matrix pb, int nrow, int ncolumn)
51 {
52     int ntemp;
53     if(str1 == NULL || pb == NULL)
54         return;
55     if(nrow == 0 || ncolumn == 0)
56         return;
57     ntemp = pb[nrow-1][ncolumn-1];
58     switch(ntemp)
59     {
60     case 1:
61         printf("locate:(%d,%d),%4c\n", nrow-1, ncolumn-1, str1[nrow-2]);//打印公共字符，这里下标是nrow-2，因为矩阵的坐标值(i,j)比字符串的实际下标大1
62         TraceBack(str1, pb, nrow-1, ncolumn-1);//向左上角递归
63         break;
64     case 2:
65         TraceBack(str1, pb, nrow-1, ncolumn);//向上方向递归
66         break;
67     case 3:
68         TraceBack(str1, pb, nrow, ncolumn-1);//向左方向递归
69         break;
70     default:
71         break;
72     }
73 }

View Code

4.最大连续子数组

class Solution {
public:
    int maxSubArray(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int ret = INT_MIN;
        int sum = 0;
        for(int i = 0; i < n; i++)
        {
            sum = max(sum + A[i], A[i]);
            ret = max(sum, ret);
        }
        
        return ret;
    }
};

这里，省去了dp[i]数组，只用一个sum表示，当前最大的数组和的值。每次更新的时候，把上次的更新掉，所以不能记录每个下标的最大sum。只能依次遍历。后面覆盖别的的sum

int maxSubArray(vector<int>& nums) {
       int len=nums.size();
       int sum=0;
       int max=INT_MIN;
       for(int i=0;i<len;i++){
           if(sum>0)
             sum+=nums[i];
           else
              sum=nums[i];
          if(sum>max)
            max=sum;
       }
       return max;
      
        
    }

动态规划习题总结

推荐阅读