背包系列问题——换零钱2

参考资料：
1. 动态规划之背包问题系列
2. 换零钱2

无限硬币》》完全背包问题
只不过把问题从最大收益换做种类，max改为+
采用分析一压缩空间做法

private int INVALID = 0;

public int change(int amount, int[] coins) {
    int[] dp = new int[amount+1];
    Arrays.fill(dp, INVALID);
    dp[0] = 1;

    for (int coin : coins) {
        for (int j = 1; j <= amount; j++) {
            int leftAmount = j - coin;
            if(leftAmount>=0){
                dp[j] = dp[j] + dp[leftAmount];
            }
        }
    }

    return dp[amount];
}