가장 긴 증가하는 부분 수열

이게머임?

• DP 알고리즘의 문제 해결 기법 중 하나로, 어떠한 수열이 주어졌을 때, 원소가 증가 혹은 감소 하는 형태(내림차순 or 오름차순)가 가장 긴 부분 수열을 찾는 방법!
• 길이가 n인 수열에서 dp 테이블의 모든 원소 값을 1로 초기화 한 후 dp[i]가 array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이라고 정하면 점화식은 아래와 같다!
  • 모든 0 <= j <  i에 대하여 dp[i] =  max(d[i], d[j] + 1) if array[j] < array[i]
  • i는 부터 n-1까지
• [10 , 20, 10, 30, 20, 50]이 있을 때 예시를 살펴보자!

 

소스코드

n = [10, 20, 10, 30, 20, 50]
dp = [1] * len(n)

for i in range(1, len(n)):
    for j in range(0, i):
        if n[i] > n[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(dp)
# [1, 2, 1, 3, 2, 4]

 

관련 문제

https://www.acmicpc.net/problem/18353

18353번: 병사 배치하기

import sys

n = int(sys.stdin.readline())
soldiers = list(map(int, sys.stdin.readline().split()))
dp = [1] * n

for i in range(1, n):
    for j in range(0, i):
        if soldiers[i] < soldiers[j]:
            dp[i] = max(dp[i], dp[j] + 1)
print(n - max(dp))