# Classic Coin Change Problem, Java DP 6 Lines

• ``````public 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) dp[i] += dp[i - coin];
}
}
return dp[amount];
}
}
``````

• you could get rid of `if (i >= coin)` by starting `i` from `coin`

• This post is deleted!

• @paplorinc yes you're right

• I was wondering what will happen if we swap the two for loops ?

• @piyush121 Then you will need to derive an equivalent formula to update dp which may not be so obvious since you must deal with duplicated cases. You can check #322 for Coin Change 1 where we could easily swap two for-loops since there we only compute min. numbers.

• @hellotest Can you come up with that formula ? I think it's not possible to solve it that way.

• @piyush121

``````class Solution {
public:
int change(int amount, vector<int>& coins) {
// DP, time: O(m*n), space: O(m*n)
// dp[i][j]: number of ways to get amount=i using the first j+1 coins
// idea: to compute dp[i][j], consider two cases: 1. include coins[j] 2. does no include coins[j]
int n = coins.size();
if (n == 0) return 1;
int dp[amount+1][n];
for (int j = 0; j < n; ++j) {
dp[0][j] = 1;
}
for (int i = 1; i <= amount; ++i) {
for (int j = 0; j < n; ++j) {
dp[i][j] = (i >= coins[j] ? dp[i - coins[j]][j] : 0) + (j >= 1 ? dp[i][j-1] : 0);
}
}
return dp[amount][n-1];
}
};
``````

However, it seems that it cannot pass the OJ for some tests.

• @piyush121 Actually that's how I solved the problem. I had to use a 2-d array dp[i][j] where i is the amount and j is the index in coins; dp[i][j] denotes ways to sum up to i while the smallest coin value picked is coins[j]. So for {1,2} 3 we have i = 1 {1, 0}, i = 2 {1, 1} and i = 3 {2, 0}. For i = 3 it's {2, 0} because 1+1+1/1+2, so 2+1 is not counted. Whenever you need to calculate dp[i][x] you have to do a range sum so performance is worse than O(mn).

``````int change(int amount, vector<int>& coins) {
if (amount == 0)
return 1;
if (coins.empty())
return 0;
sort(coins.begin(), coins.end());
vector<vector<int>> helper(amount + 1, vector<int>(coins.size(), 0));
// helper[i][j] means ways of producing i while min coin value is coins[j].
for (int i = coins[0]; i <= amount; ++ i) {
for (int j = 0; j < coins.size(); ++ j) {
if (i - coins[j] < 0)
break;
if (coins[j] < i) {
if (i - coins[j] >= coins[j])
helper[i][j] = accumulate(helper[i - coins[j]].begin() + j, helper[i - coins[j]].end(), 0);
}
else if (coins[j] == i) {
helper[i][j] = 1;
break;
}
else
break;
}
}
return accumulate(helper[amount].begin(), helper[amount].end(), 0);
}
``````

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