[백준] 11052 . 카드 구매하기 - 파이썬

N = int(input())
dp = [0]+list(map(int,input().split()))
#합이 N인것의 조합, dp[i]에 최댓값 갱신
for i in range(N+1):
    for j in range(1,i+1):
        dp[i] = max(dp[i],dp[i-j]+dp[j])
print(dp[N])

---

인덱스를 맞추기위해 [0]앞에 더해줬다.

N을 만들 수 있는 조합을 찾기 위해 j 인덱스를 해당 인덱스i까지 증가시키면서 반복문을 돌린다.

여기서 점화식dp[i-j]+dp[j]가 쓰인다.