Knapsack Problem (Java) - ShuweiLeung/Thinking GitHub Wiki

背包问题

1.（518:Medium）（非常非常经典题）Coin Change 2

• This is a classic knapsack problem.

dp[i][j] : the number of combinations to make up amount j by using the first i types of coins

State transition:

1. not using the ith coin, only using the first i-1 coins to make up amount j, then we have dp[i-1][j] ways.
2. using the ith coin, since we can use unlimited same coin, we need to know how many ways to make up amount j - coins[i-1] by using first i coins(including ith), which is dp[i][j-coins[i-1]]。这里有个累计的概念，我们只要知道了前i个coins组成j-coins[i-1]的种类个数，就包括了j-coins[i-1]*2的种类数了

Initialization: dp[i][0] = 1