🙈 동적 계획법

2020년 올해의 마지막 블로그를 작성하겠습니다.

동적 계획법이란?

복잡한 문제를 재귀를 통해 간단한 하위 문제로 분류 및 단순화하여 해결하는 방법
최적 부분 구조 / 중복되는 부분 문제가 있다면 동적 계획법을 사용하면 좋습니다.
최적부분구조 : 답을 구하기 위해 했던 계산을 반복해야하는 구조

최장 증가 부분열 찾기

1. 동적계획법

from bisect import bisect
from itertools import combinations
from functools import wraps

def solution(seq):
    L = [1] * len(seq)
    res = []
    for cur, val in enumerate(seq):
        for i in range(cur):
            if seq[i] <= val:
                L[cur] = max(L[cur], 1 + L[pre])
    return max(L)