518. Coin Change 2

 一刷 06/2022

Version #1 DP

自己没做出来

这道题和combination sum 4 的区别是，不同的顺序会当成同一个答案

在combination sum的时候，(1,1,2)和(2,1,1)是不一样的，所以outer loop iterate over sum，inner loop iterate over number

这道题(1,1,2)和(2,1,1)是同一个答案，所以要保证一个顺序，比如前面的数先选，所以outer loop iterate over numbers, inner loop iterate over sum

Time O(N*amount)

Space O(amount)

Runtime: 7 ms, faster than 57.10% of Java online submissions for Coin Change 2.

Memory Usage: 42.2 MB, less than 58.74% of Java online submissions for Coin Change 2.

class Solution {

    public int change(int amount, int[] coins) {

        int[] dp = new int[amount + 1];

        dp[0] = 1;

        for (int coin : coins) {

            for (int i = 1; i <= amount; i++) {

                if (i - coin >= 0) {

                    dp[i] += dp[i - coin];

                }

            }

        }

        return dp[amount];

    }

}