518. Coin Change II

518. Coin Change II

https://leetcode.com/problems/coin-change-ii/

문제

풀이

amount가 0~5일 때, coins이 0,1,2,5일 때 각각 분할 정복해서 푸는 문제이다.
amount = 2이고 coins 2일 때를 생각해보자
coins 2를 사용하지 않을 때에는 표에서 바로 위에 값(coins 1에서만 사용했을 때) 1과, coins 2를 사용했을 때 dp(2,0)을 더해야 한다. 경우의 수는 ((1+1+1), (2))가 될 것이다.
amount = 2이고 coins 4일 때를 생각해보자
coins 2를 사용하지 않을 때에는 표에서 바로 위에 값(1)과, coins 2를 사용했을 때 dp(2,3)을 확인해야 한다. 경우의 수는 ((1+1+1+1), (1+1+2),(2+2)) = 3이라는 것을 확인 할 수 있다.
마찬가지로 coins 5이고 amount가 5일 때에는 사용하지 않았을 때 (1+1+1)과 자기 자신(1)을 더한값인 4를 리턴하게 된다.

결과