518. Coin Change II - Medium

前往題目

思路

好多種解法，應該說有很多優化的方式，大致上遵循以下規則

1. bottom-up的方式，從最基礎的case(amount = 0無論是任何硬幣都有一種可能可以達成)開始
2. 疊代不同的硬幣慢慢的加上所有可能性

這題畫二維陣列就會很清楚了

Code

只使用DFS會超時，因為每次都要重算

// TLE
class Solution {
    private Map<Pair<Integer, Integer>, Integer> cache;

    public int change(int amount, int[] coins) {
        cache = new HashMap<>();
        return dfs(0, 0, amount, coins);
    }

    private int dfs(int i, int a, int amount, int[] coins) {
        if (a == amount)
            return 1;
        if (a > amount)
            return 0;
        if (i == coins.length)
            return 0;
        if (cache.containsKey(new Pair<>(i, a)))
            return cache.get(new Pair<>(i, a));

        cache.put(new Pair<>(i, a), dfs(i, a + coins[i], amount, coins) + dfs(i + 1, a, amount, coins));
        return cache.get(new Pair<>(i, a));
    }
}

Memoization

// T: O(m * n)
// S: O(m * n)
class Solution {
    public int change(int amount, int[] coins) {
        int[][] dp = new int[amount + 1][coins.length + 1];

        // Amount 0, any coin can reach with 1 possibility
        for (int i = 0; i < coins.length; ++i) {
            dp[0][i] = 1;
        }

        // bottom up，從最小值開始一步一步加上可能性
        for (int a = 1; a <= amount; ++a) {
            // 從大的硬幣開始
            for (int i = coins.length - 1; i >= 0; --i) {
                // 看下一個硬幣，因為下一個的結果再加上這次的結果就是當前的所有可能性
                dp[a][i] = dp[a][i + 1];
                // 如果可以再加硬幣
                if (a - coins[i] >= 0) {
                    // 加上給出硬幣後的可能性
                    dp[a][i] += dp[a - coins[i]][i];
                }
            }
        }

        // 回傳所有可能性
        return dp[amount][0];
    }
}

More optimised solution，只用一維陣列

// T: O(m * n)
// S: O(n)
class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int i = coins.length - 1; i >= 0; --i) {
            int[] nextDp = new int[amount + 1];
            nextDp[0] = 1;

            for (int a = 1; a <= amount; ++a) {
                nextDp[a] = dp[a];
                if (a - coins[i] >= 0) {
                    nextDp[a] += nextDp[a - coins[i]];
                }
            }
            dp = nextDp;
        }
        return dp[amount];
    }
}