최대부분증가수열 (DP) 복기

코드

#i의 이전 리스트를 돌면서 가장 큰값을 선택

N = int(input())
graph = list(map(int, input().split()))

memo = []

memo.append(1)
for i in range(1,len(graph)):
    max_length = 0
    for j in range(i):
        if graph[j] < graph[i]:
            max_length = max(max_length, memo[j])
    memo.append(max_length+1)


print(max(memo))

생각해 봐야할 것

• 가장 작은 것 부터 생각한다. (bottom - up)

• 가장 작은 것은 첫번째 숫자만 증가 수열로 가지고 있는 것이다.

• 메모지제이션에는 현재 숫자를 마지막으로 가지는 최대 증가 수열의 크기를 저장한다.

• 이때 현재 숫자 이전의 값들 중에서 다음으로 올 수 있는 숫자를 선택하는 것이다.

• 메모지제이션에는 현재 자신을 마지막으로 하는 증가수열 수의 최대값을 저장

• 이것을 어떻게 찾냐면 이전 값들 중에서 다음으로 올 수 있는 증가수열 하나를 선택해서 붙여준다.