퉁탕퉁탕 만들어보자

https://www.hackerrank.com/challenges/coin-change/problem?isFullScreen=true The Coin Change Problem | HackerRank Given a list of 'm' coin values, how many ways can you make change for 'n' units? www.hackerrank.com 문제) 갖고있는 동전 배열이 있다. 배열의 각각의 수는 동전의 값을 의미한다 (1원, 3원..) 동전의 갯수는 무한이라고 친다. n원을 거슬러줘야 할 때, n원을 만드는 동전의 조합의 수를 구하라 예제) Sample Input 타겟금액, 동전갯수 동전 액면가들 4 3 1 2 3 Sample Output 4 Explanation ..

동적프로그래밍은 간단하게 생각하면, 이전에 도출된 해를 가지고 그 다음 해를 구하는 식으로 푸는것이다. 그러면 이게 문제를 점화식으로 나타낼 수 있는데, 점화식만 도출해 내면 코드는 아주 짧다. 가장 유명하고 쉬운 문제는 피보나치 수열이다. 피보나치 수열은, 처음 두 값이 주어진다. 수열의 n번째 값을 F(n) 이라고 할 때, F(0) = 0, F(1) = 1 이 주어진다. 그 다음으로 오는 수는 바로 이전 두 값의 합이다. F(0) = 0, F(1) = 1 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(2) + F(1) = 1 + 1 = 2 F(4) = F(3) + F(2) = 2 + 1 = 3 ... [0,1, 1, 2, 3, 5, .... ] 이렇게 나가게 되며, 점화식으로..