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];
}
}
Classic Coin Change Problem, Java DP 6 Lines


@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 forloops 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.

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][j1] : 0); } } return dp[amount][n1]; } };
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 2d 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); }