[LeetCode] 518. Coin Change II - 동적계획법(Dynamic Programming) + 깊이우선탐색(DFS) JAVA

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

코드설명

동적계획법(Dynamic Programming) + 깊이우선탐색(DFS) 을 활용합니다.

 

이 문제가 동적계획법, 즉 최적부분구조가 성립하는 이유를 예제1로 예시를 들어보겠습니다.

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

1원으로 만들 수 있는 경우.

1원 = 1 = 1가지

2원 = 1 + 1 = 1가지

3원 = 1 + 1 + 1 = 1가지 

 

2원으로 만들 수 있는경우

2원 = 2 = 1 가지

3원 = (3- 2원) = 1원으로써  = 1가지 (1 + 2) 입니다.

 

최종적으로 3원은 = {1 + 1 + 1, 1 + 2} 입니다.

코드

class Solution {
    int[] Coins;
    int[][] cache = new int[301][5001];
    int Amount;
    public int change(int amount, int[] coins) {
        Coins = coins;
        Amount = amount;
        for(int[] v : cache){
            Arrays.fill(v, -1);
        }
        return DFS(0, amount);
    }

    int DFS(int idx, int money){
        if(money == 0) return 1;
        if(idx == Coins.length) return 0;
        if(cache[idx][money] != -1) return cache[idx][money];

        int ret = 0;
        if(money - Coins[idx] >= 0){
            ret += DFS(idx, money - Coins[idx]);
        }
        ret += DFS(idx + 1, money);

        return cache[idx][money] = ret;
    }
}