[알고리즘] 다이나믹 프로그래밍(Dynamic Programming) - 설명, 예제

다이나믹 프로그래밍(Dynamic Programming) :최적화 문제를 해결하는 알고리즘 기법. 점점 긴 길을 걷다보면서 이전에 겪었던 길의 결과를 저장하여 더 짧은 길을 걸을 수 있는 것처럼, 다이나믹 프로그래밍에서는 이전에 계산한 결과를 저장하여 다음에 필요할 때 더 빠르게 계산한다.

마치 쇼핑몰에서 자주 구매하는 상품은 미리 장바구니에 담아두어 다음에 구매할 때 더 빠르게 처리하는 것과 같다. 출처 : DALL-E 예제 - 계단 오르기 주어진 계단을 오르는데 각 계단에서는 1계단 또는 2계단씩만 오를 수 있다.

계단 오르기 경로의 점수의 합의 최대 값을 구하려고 한다. - 계단 점수: (10, 20, 15, 25, 10, 20) 해답 및 설명 with python def climb_stairs(scores): n = len(scores) dp = [0 for i in range(n)] dp[0] = scores[0] dp[1] = max(scores[0] + scores[1]...