knapsack

DP 메모이제이션(memoization) 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술 → 동적 계획법의 핵심 기술! ex) 피보나치 수열의 재귀: 중복호출을 반복하게 됨 # memo를 위한 배열을 할당하고, 모두 0으로 초기화 한다. # memo[0]을 0으로 memo[1]은 1로 초기화 한다. fibo(n) IF n>=2 AND memo[n] = 0 memo[n] w K[i, w]