# Knapsack problem - Java solution with thinking process O(nm) Time and O(m) Space

• This is a classic knapsack problem. Honestly, I'm not good at knapsack problem, it's really tough for me.

`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 `i`th coin, only using the first `i-1` coins to make up amount `j`, then we have `dp[i-1][j]` ways.
2. using the `i`th coin, since we can use unlimited same coin, we need to know how many way to make up amount `j - coins[i]` by using first `i` coins(including `i`th), which is `dp[i][j-coins[i]]`

`Initialization`: `dp[i][0] = 1`

Once you figure out all these, it's easy to write out the code:

``````    public int change(int amount, int[] coins) {
int[][] dp = new int[coins.length+1][amount+1];
dp[0][0] = 1;

for (int i = 1; i <= coins.length; i++) {
dp[i][0] = 1;
for (int j = 1; j <= amount; j++) {
dp[i][j] = dp[i-1][j] + (j >= coins[i-1] ? dp[i][j-coins[i-1]] : 0);
}
}
return dp[coins.length][amount];
}
``````

Now we can see that `dp[i][j]` only rely on `dp[i-1][j]` and `dp[i][j-coins[i]]`, then we can optimize the space by only using one-dimension array.

``````    public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i-coin];
}
}
return dp[amount];
}
``````

• In knapsack every item has two attributes (i.e weight and a value) but in this problem every coin has just 1 attribute the value. How can you compare it to knapsack? Perhaps I did not understand your thought process correctly. i understand that every time you have to choose between whether to pick this coin or not. But still when I think about the original coin change problem i get confused. Could you please elaborate ?

• `for (int i = coin;...)` the initial of `i` is really beautiful. Thanks!

• Still have difficulty to understand why the solution is the sum of case using `i`th coin and case not using `i`th coin and Why this is sufficient. anyone could share any illustration to help?

• Hi all!

Can you please explain the difference between this solution - O(m) space complexity - and the following one:

https://discuss.leetcode.com/topic/52302/1ms-java-dp-solution-with-detailed-explanation/

I am interested in the way this solution does not count the same combination more than once while the other does.

Thanks!

• The difference is that if you update `dp` while:

• increasing `i` then the previous partial result `dp[i - coin]` is the result that has considered `coin` already
• decreasing `i` then the previous partial result `dp[i - coin]` is the result that has not considered `coin` yet
``````/**
* @return number of ways to make sum s using repeated coins
*/
public static int coinrep(int[] coins, int s) {
int[] dp = new int[s + 1];
dp[0] = 1;
for (int coin : coins)
for (int i = coin; i <= s; i++)
dp[i] += dp[i - coin];
return dp[s];
}

/**
* @return number of ways to make sum s using non-repeated coins
*/
public static int coinnonrep(int[] coins, int s) {
int[] dp = new int[s + 1];
dp[0] = 1;
for (int coin : coins)
for (int i = s; i >= coin; i--)
dp[i] += dp[i - coin];
return dp[s];
}
``````

• This post is deleted!

• A question on why we have `Initialization: dp[i][0] = 1`, as described by tankztc, `dp[i][j]` represent the number of combinations to make up amount `j` by the first `i` types of coins, so `dp[i][0]` should represent the number of combinations to make up `0` by the first `i` types of coins, the number of combinations is `0`, so `dp[i][0] = 0` right ? Why initialize as `1` ?

Have a tricky perspective: use no coins (auto deduct result as amount = 0) is actually 1 method (or understand as use no coins is also a kind of combination) ? Not sure if any better perspective than this explain ?

• @lampard08 I do not think OP's initialization is correct. The correct initilization should be: dp[0][0] = 1 and dp[i][0] = 0 and dp[0][i] = 0

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.