DP 개념정리하기 (2)

---

String Matching

---

아이템을 적절히 고르는 문제

 

 

지금까지 선택한 동전의 합이 i 라 했을 때, 가능한 최대 동전의 개수

이렇게 테이블을 만든 이유 :

문제에서 동전의 최대 개수를 구하는 것이기 때문에

돈을 작은 돈 부터 풀어나가자는 바텀업으로 진행,

동전의 합에 따른 최대 개수를 그대로 테이블화

 

점화식 만들 때

1. 상황 나누기

마지막 상황 즉, 마지막에 무엇을 더하는 것에 따라 조건문을 만든다.

10을 거슬러줘야 할 때, 이런 경우의 수가 있다.

2+2+2+2+2 

2+2+3+3

2+4+4

3+3+4

어떻게 나눠야 할까?

마지막에 선택되는 동전으로 나누기

2+2+2+2+2

/

2+2+3+3

/

2+4+4

3+3+4

 

2. 하나의 상황에 대한 점화식

마지막으로 2를 더하는 모든 상황 중, max를 선택한다.

2를 더하기 전의 합이 6과 8이 있으면 8을 선택하고 2를 더하도록.

import sys
INT_MIN = -sys.maxsize

n, m = 3,8
dp = [0] * (m+1)
coin = [0,3,4,5]

def initialize():
	for i in range(m + 1):
    	dp[i] = INT_MIN
        
    dp[0] = 0
    
initialize()

for i in range(1, m+1):
	for j in range(1, n+1):
    	if i >= coin[j]:
        	if dp[i-coin[j]] == INT_MIN:
            	continue
            dp[i] = max(dp[i], dp[i-coin[j]]+1)

---

조건에 맞게 선택적으로 전진하는 DP

1. 테이블 정의

2. 초기값

3. 점화식

이 방식으로 DP 풀기

 

1. 테이블 정의

dp[i] = i 항의 위치에서 점프한 최대 횟수