Classic Coin Change Problem, Java DP 6 Lines


  • 5
    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];
        }
    }
    

  • 4

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


  • 0
    This post is deleted!

  • 0

    @paplorinc yes you're right


  • 2
    P

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


  • 0
    H

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


  • 0
    P

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


  • 0
    H

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


  • 0
    A

    @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);
    }
    

Log in to reply
 

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