welcome
0%

最长公共子序列的长度

发表于 更新于 分类于

代码：
递归公式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
using namespace std;
int find(int *a,int len,int x)
{
	int left=0,right=len,mid=(left+right)/2;
	while(left<=right)
	{
		if(x>a[mid]) left=mid+1;
		else
		if(x<a[mid]) right=mid-1;
		else
		return mid;
		mid=(left+right)/2;
 } 
 return left;
}
int main()
{
	int i,j,n,a[100],c[100],len;
	cin>>n;
	for(i=0;i<n;i++)
	cin>>a[i];
	for(i=0;i<n;i++)
	{
		c[i]=1000;
	}
	len=1;
	c[0]=a[0];
	for(i=1;i<n;i++)
	{
       j=find(c,n,a[i]);//二分查找 
       c[j]=a[i];
       if(j>len)
       len=j+1; 
	}
	cout<<len;
}

1、递归方程：
b[++len] = a[i];　　a[i] > b[len];
b[j] = a[i];　　a[i] <= b[len];
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
using namespace std;

int a[1005], b[1005];

int binary_search(int len, int i){
    int first = 1, last = len;
    while(first < last){
        int mid = first + (last - first) / 2;
        if (b[mid] >= a[i])
            last = mid;
        else
            first = mid + 1;
    }
    return first;
}

int main(){
    int n; 
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    b[1] = a[0];
    int len = 1;
    for (int i = 1; i < n; i++){
        if (a[i] > b[len]){
            b[++len] = a[i];
        }
        else {
            int j = binary_search(len, i);
            b[j] = a[i];
        }
    }
    printf("%d\n", len); 
    return 0;
}

2、 递归方程：
dp[i] = max(dp[i], dp[j] + 1);　　a[j] < a[i];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#define MAX_N 1000

int dp[MAX_N], a[MAX_N];
int n;

int max(int a, int b){
    return a > b? a: b;
}

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    
    int res = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < i; j++){
            if (a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }
        res = max(dp[i], res);
    }
    printf("%d", res + 1);
    return 0;
}