거스름돈

[geonnho0]

문제 링크

[geonnho0]

dp 배열의 정의는 다음과 같아요.

• dp[i][j] : i원을 거스를때, 사용한 동전의 최대 값이 j일 경우의 모든 수

정의에 따라서 (i, j)일 경우, 먼저 (i, j - 1)일 경우와 값이 같아요.

점화식

• dp[i][j] = dp[i][j - 1] + dp[i - money[j]][j]

코드

class Solution {
    final int MOD = 1000000007;

    public int solution(int n, int[] money) {
        int m = money.length;
        int[][] dp = new int[n + 1][m + 1];
        Arrays.sort(money);
        for (int i = 0; i < m; i++)
            dp[money[i]][i + 1] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] += dp[i][j - 1];
                int left = i - money[j - 1];
                if (left < 0)
                    continue;
                dp[i][j] = (dp[i][j] + dp[left][j]) % MOD;
            }
        }
        return dp[n][m] % MOD;
    }
}