1import sys
2input = sys.stdin.readline
3N = int(input())
4T = []
5P = []
6dp = [0]*(N+1)
7
8for _ in range(N):
9 a, b = map(int, input().split())
10 T.append(a)
11 P.append(b)
12
13for i in range(N-1, -1, -1):
14 if i+T[i] > N:
15 dp[i] = dp[i+1]
16 else:
17 dp[i] = max(P[i]+dp[i+T[i]], dp[i+1])
18
19print (dp[0])
- dp라는 변수를 만들어야하는데 안 만들고 리스트 P만 가지고 memoization 하려다 실패했다
- 점화식은 잘 적었으나 조건문이 잘 못되어서 다른 풀이를 참고했다