bright

기본 식 : dp[i] = MAX(P[i] + dp[i+T[i]], dp[i+1])

n = int(input())

t = [0 for _ in range(n)]
p = [0 for _ in range(n)]

for i in range(n):
  t[i],p[i] = map(int,input().split())


dp = [0 for _ in range(n)]
if t[n-1] == 1 : 
  dp[n-1] = p[n-1]


for i in range(n-2, -1, -1):
  day = i + t[i]

  if day == n : 
    # 더 이상의 상담은 없음. 
    dp[i]= max(p[i], dp[i+1])
  elif day < n : 
    dp[i] = max(p[i]+dp[day], dp[i+1])
  elif day > n : 
    dp[i] = dp[i+1]
  
print (max(dp))

# Reference 

https://bcp0109.tistory.com/8

t = int(input())
n = []
for i in range(t):
  n.append(int(input()))

data= [0]*101 

data[0]=1
data[1]=1
data[2]=1
data[3]=2
data[4]=2

for i in range( 5, max(n)+1):
  if data[i] == 0:
     data[i] = data[i-1]+data[i-5]

for i in n:
  print(data[i-1])

n = int(input())

data=[0]*1001

data[1]=1

if n > 1:
  data[2]=3

  for i in range(3,n+1):
    data[i]= data[i-2]*2+data[i-1]

print(data[n]% 10007)

n = int(input()) # 1<=n<=100   # 0 ~ 9 인데, 0은 맨 처음에 올 수 x 

data = [ [0,0,0,0,0,0,0,0,0,0] for i in range(n+1) ] 

for i in range(1,10):
  data[1][i]=1

if n>1:
  data[2][0]=1
  data[2][1]=1
  for i in range(2,9):
    data[2][i]=2
  data[2][9]=1

  for i in range(3,n+1):
    for j in range(10):
      if j == 0 :
        data[i][j] = data[i-1][j+1]
      elif j == 9 : 
        data[i][j] = data[i-1][j-1]
      else:
        data[i][j] = data[i-1][j-1]+data[i-1][j+1]

print(sum(data[n])%1000000000)

n = int(input())
data = list(map(int,input().split()))

m = [1]*n

for i in range(n):
  for j in range(i):
    if data[j] < data[i]:
      m[i] = max( m[j]+1, m[i])

print(max(m))

- 점화식 헷갈리면 외워두기 

- 만약 나보다 전 인덱스에 나보다 작은 값이 있다면, 그 값을 포함하는 것과 현재 값 중 큰 값 고르기 

# 다른 폴이

n = int(input())
answer = list(map(int, input().split()))
dp = [0] * n

for i in range(0, n):
    if i == 0 :
        dp[i] = 1
    else :
        max_dp = 0
        for j in range(0, i):
            if max_dp < dp[j] and answer[j] < answer[i]:
                max_dp = dp[j]
        dp[i] = max_dp+1

print(max(dp))

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