백준 11055번 파이썬 문제풀이(가장큰 증가 부분 수열) - DP(탑다운)

---

현재 고른 위치와 전에 고른 위치를 dp에 저장해서 다음번에 도착시 해당 dp에 저장된 값을 리턴하도록 코드를 구현했다.

 

import sys

sys.setrecursionlimit(10000)
N = int(input())
arr = list(map(int, input().split())) + [0]

dp = [[-1] * (N + 1) for _ in range(N + 1)]


def recur(cur, pre):
    if cur >= N:
        return 0

    if dp[cur][pre] != -1:
        return dp[cur][pre]

    if arr[cur] > arr[pre]:
        dp[cur][pre] = max(recur(cur + 1, cur) + arr[cur], recur(cur + 1, pre))
    else:
        dp[cur][pre] = recur(cur + 1, pre)

    return dp[cur][pre]


print(recur(0, -1))