动态规划5(常见面试题)

参考:《编程之美》《算法导论》http://blog.csdn.net/jiang_bing/article/details/7357044

1,最大连续子串之和:

这个问题很简单既不多说了具体参考http://blog.csdn.net/zh533749/article/details/11907421;

2,最长递增子串:

例如 1,-1,2,-3,4,-5,6,-7最长递增子串为 1,2,4,6.

首先给出递归方程:


LIS即为我们存储的子结果初始化都为1,每次我们都搜索原array,如果array[i + 1]>array[k]那么我们将最大的LIS[k] +1赋给LIS[i+1].

最后遍历一遍LIS我们就能找出最大的第增字串。

3,LCS(最长公共子序列不一定连续



这个算法导论中讲的比较详细在此就不多讲了下面给出程序:

#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<string.h>
using namespace std;
#define raw 10
#define colum 10

#define MAX(a,b)  ((a) >=(b)? a:b) 

int LCSTemp[raw][colum] = {0};

void LCS(char string1[], char string2[])
{
        int len1 = strlen(string1);
        int len2 = strlen(string2);
        int i,j;
        
        for(j = 0; j < len1; j++)
                LCSTemp[0][j] = 0;
        for(i = 0; i < len2; i++)
                LCSTemp[i][0] = 0;
        for(i = 1; i <len1; i++)
                for(j = 1; j < len2; j++)
                {
                        if(string1[i] == string2[j])
                                LCSTemp[i][j] = LCSTemp[i-1][j-1] + 1;
                        else 
                        {
                                LCSTemp[i][j] = MAX(LCSTemp[i-1][j], LCSTemp[i][j-1]);
                        }
                 }
}

int main()
{
      char string1[100];
      char string2[100];
      printf("intput string1:");
      scanf("%s", string1);
      printf("input string2:");
      scanf("%s", string2);
      LCS(string1, string2);
      int i,j;
      
      int len1 = strlen(string1);
      int len2 = strlen(string2);
      for(i = 0;i < len1; i++)
      {
        for(j = 0; j <len2; j++)
                printf("%d ", LCSTemp[i][j]);
        printf("\n");
      }
}
结果:

4,LIS(最长连续公共子串)

例如:aabcddjj,vabcddsd这两个字符串中红色部分即为LIS结果,与LCS不同的是LIS要求该串必须连续递归方程如下:


#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<string.h>
using namespace std;
#define raw 10
#define colum 10

#define MAX(a,b)  ((a) >=(b)? a:b) 

int LCSTemp[raw][colum] = {0};
void LIS(char string1[], char string2[])
{
        int len1 = strlen(string1);
        int len2 = strlen(string2);
        int i,j;
        for(j = 0; j < len1; j++)
                LCSTemp[0][j] = 0;
        for(i = 0; i < len2; i++)
                LCSTemp[i][0] = 0;
         for(i = 1; i <len1; i++)
                for(j = 1; j < len2; j++)
                {
                        if(string1[i] == string2[j])
                                LCSTemp[i][j] = LCSTemp[i-1][j-1] + 1;
                        else 
                        {
                                LCSTemp[i][j] = 0;
                        }
                 }
}  


int main()
{
      char string1[100];
      char string2[100];
      printf("intput string1:");
      scanf("%s", string1);
      printf("input string2:");
      scanf("%s", string2);
      LIS(string1, string2);
      int i,j;
      
      int len1 = strlen(string1);
      int len2 = strlen(string2);
      for(i = 0;i < len1; i++)
      {
        for(j = 0; j <len2; j++)
                printf("%d ", LCSTemp[i][j]);
        printf("\n");
      }
}
      

LCS,LIS,最短编辑距离,都是同一类问题,解决方法也类似,我们可以再用额外数组保存路径结果,这个和算法导论上的类似,大家可以参考《算法导论》

相关文章
相关标签/搜索