[알고리즘] 동적 프로그래밍

동적 프로그래밍

• 한번 계산한 값은 다시 구하지 않습니다. 작은 문제에 대해 구한 값을 저장하고, 큰 값을 구할때 먼저 계산했던 값을 사용합니다.

• 동적 프로그래밍 문제를 풀기 위해서는 점화식 (인접한 항들 사이의 관계식)을 세워야 합니다.

  • 예 : dp[i]의 값을 구해야 할 때, 앞에 있는 값을 어떻게 사용해서 i의 값을 구할 수 있는지 관계식을 도출해야합니다.

쉽지 않습니다...ㅠ

동적 프로그래밍 문제 LIST

• 백준 : 평범한 배낭, 01타일, 가장 긴 증가하는 부분 수열
• 백준 다이나믹 프로그래밍 기초 문제집
• 프로그래머스 동적계획법 모음