[アルゴリズム]動的計画の基礎

# memo 배열을 할당하고, 모두 0으로 초기화
# memo[0]을 0으로 memo[1]은 1로 초기화

def fibo(n):
	if n>=2 and memo[n] = 0:
    		memo[n] = fibo(n-1) + fibo(n-2) # 처음 계산되는 값이라면 값 저장
	return memo[n]

1) 최적화 문제 해결 : 최대값/최소값 구하는 문제, 여러 개의 최적해 중 임의의 최적해 하나를 찾는 것
2) 완전 검색을 좀 더 효율적으로 하는 방법
3) 재귀 + 메모이제이션
4) 점화식을 찾으면 됨 : 문제를 분석하여 재귀적 정의 및 수식 형태 표현 필요

- 순환적인 관계(recurrence relation)의 명시적 표현 : 점화식 사용
- 문제의 순환적 성질로 이전에 계산된 작은 문제의 해가 더 큰 문제의 해를 구할 때 중복으로 사용됨
- 메모이제이션 사용
- 이미 해결한 작은 문제의 해가 다시 필요할 때 테이블을 참조하여 중복 계산을 피함

- 주어진 문제가 최적화의 원칙을 만족해야 동적 계획법을 효율적으로 적용 가능
- 최적화 원칙 : 어떤 문제에 대한 해가 최적일 대 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 함

1) 최적해 구조의 특성 파악 : 문제를 더 작은 부분 문제로 나눔
2) 최적해 값의 재귀적 정의 : 부분 문제들의 최적 해를 사용하여 더 큰 문제의 최적해 값 정의(점화식 사용 가능)
3) 상향식 방법으로 최적해 값 계산 : 의존성에 위배되지 않도록 가장 작은 부분문제부터 해를 구하고 테이블 저장, 이를 이용하여 상위 문제 해결

f = [] * n

def fibo_dp(n):
	f[0] = 0
    f[1] = 1
    for i in range(2, n):
    # n=2인 문제부터 시작해서 큰 문제를 해결해나감
    	f[i] = f[i-1] + f[i-2]
    return f[n] # n번째 인덱스에 n번째 피보나치 수가 저장된 상태

change = 0 # 거스름돈
coin = [6,4,1]
memo = []*n

def coin_change(change):
	memo[0] = 0 # 거스름돈이 0일때는 0개의 동전이 필요
    for n in range(1,change):
    		n_min = 9999999 # 무한대
            for i in range(1, len(coin)-1):
            	if n>=coin[i]:
                	if memo[n-coin[i]] < n_min :
                    	#현재 선택한 동전의 금액을 차감한 금액이 최소값인지 계산
                    		n_min = memo[n-coin[i]]
             memo[n] = n_min +1
    return memo[change] # 거스름돈이 change일 때 필요한 최소 동전 갯수를 반환
                    	

n = 정수
k = n보다 같거나 작은 수

def bino(n,k):
	if k==0 or n==k:
		return 1
	else:
		return bino(n-1, k-1) + bino(n-1, k)

def bino(n,k):
	B = [[] for _ in range(N)]
	for i in range(0,n):
		for j in range(0, min(i,k)):
			if j == 0 or j == i:
				B[i][j] = 1
			else:
				B[i][j] = B[i-1][j-1] + B[i-1][j]
	return B[n][k]