3/27 DP(Dynamic Programming)

큰 문제를 작은 부분 문제로 나누어 해결

부분 문제의 결과를 저장하여 재사용

중복 계산을 제거하여 효율성 향상

 

피보나치 수열 [재귀 O(2^n)] -> [DP O(n)] 으로 극적인 성능 향상!

 

메모이제이션

- 계산 결과를 memo에 저장

- 같은 값을 다시 계산할 필요 없음

- 캐싱과 유사한 개념

 

DP가 필요한 경우

1. 최적 부분 구조: 부분 문제의 최적해로 전체 최적해 구성

2. 중복 부분 문제: 같은 문제가 반복적으로 등장

 

 

https://leetcode.com/problems/house-robber/description/?envType=study-plan-v2&envId=top-interview-150

House Robber - LeetCode

 

연속 해서 집을 털 수 없다.

dp 배열을 어떻게 정의 해야 할지가 중요하다

dp[n]= n번째까지 집을 털었을 경우 최대 금액

nums 에 각 집의 소지액을 나타내는 정수 배열이 주어졌다.

 

max( n번째 집을 선택했을 경우, n번째 집을 선택하지 않았을 경우 )

n번째 집을 선택했을 경우) 연속된 n-1번째는 선택하지 못한다. -> nums[n] + dp[n-2]

n번째 집을 선택하지 않았을 경우) n-1번째까지의 최댓값이 된다.

dp[n]= max(dp[n-2] + nums[n], dp[n-1])