백준 11055 [가장 큰 증가 부분 수열] 파이썬

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

11055번: 가장 큰 증가 부분 수열

import sys
input = sys.stdin.readline
N = int(input())
lst = list(map(int, input().split()))
dp = []
for i in range(len(lst)):
    dp.append(lst[i])
for i in range(N):
    for j in range(i):
        if lst[i] > lst[j]:
            dp[i] = max(dp[i], dp[j]+lst[i])
print(max(dp))

대표적인 dp 문제이다.

dp를 0으로 초기화하는것이 아닌, dp에 처음값을 저장하는것이 포인트이다.