동태 계획: 최 장 상승 서브 시퀀스 문제

10347 단어 데이터 구조 
LIS（Longest Increasing Subsequence）        
      bi， b1 < b2 < … < bS   ，           。
  ，    (1, 7, 3, 5, 9, 4, 8)，          ， (1, 7), (3, 4, 8)  。            4，     (1, 3, 5, 8). 
       ，            。

    
5
4 2 3 1 5

    ：
3

배열 dp 로 통 항 을 구 합 니 다: dp [i] = max (1, dp [j] + 1) 즉 i + 1 개 수 를 마지막 으로 하 는 최 장 상승 서브 시퀀스 길이 = 최대 (i 만 포함, j 포함)
제약 조건 i = 0: n j = 0: i 를 찾 아 a [i] > a [j] 일 때 만 판단 한다.
그러면 코드 는 다음 과 같 습 니 다.
#include
#include
using namespace std;
#define MAX_N 1000
#define MAX_I 1000000
int dp[MAX_N];
int a[MAX_I];
int n;

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

이러한 시간 복잡 도 는 O (n ^ 2)
dp [i]: = i + 1 개 수의 가장 작은 수 는 dp 를 INF (가장 큰 값) dp [i] = min (dp [i], a [i]) 로 초기 화 합 니 다.
#include
#include
using namespace std;
#define MAX_N 1000
#define INF 999999
int a[MAX_N];
int dp[MAX_N];

int main()
{
	int n;
	cin >> n;
	for (int i=0;i < n;i++)
	{
		cin >> a[i];
	}
	for (int i = 0;i < n;i++)
	{
		dp[i] = INF;
	}
	for (int i = 0;i < n;i++)
	{
		*lower_bound(dp, dp + n, a[i]) = a[i];
	}
	printf("%d
", lower_bound(dp, dp + n, INF) - dp);
	getchar();
}

이렇게 시간 복잡 도 는 O (nlogn) 로 변 한다.
C Shell (쉘 스크립트)
제7 장 실험: 그림 의 인접 행렬, 인접 표 표시 와 기본 조작

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage