We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. DP: Coin Change
  2. Discussions

DP: Coin Change

Sort by

recency

|

96 Discussions

|

  • omkpatel110
     + 0 comments

    include

    include

    include

    using namespace std;

    vector coinChangeDP(const vector& coins, int amount) { vector dp(amount+1,numeric_limits::max()); dp[0]=0;

    for(int i=1;i<=amount;i++)
{
    for(int j=0;j<coins.size();j++)
    {
        if(coins[j]<=i && dp[i - coins[j]] != numeric_limits<int>::max())
        {
            dp[i] = min(dp[i], dp[i - coins[j]] + 1);
        }
    }
}
if(dp[amount]==numeric_limits<int>::max())
{
    return {-1};
}
else
{
    vector<int> result;
    int remaining = amount;
    while (remaining > 0) {
        for (int j = 0; j < coins.size(); j++) {
            if (remaining >= coins[j] && dp[remaining - coins[j]] == dp[remaining] - 1) {
                result.push_back(coins[j]);
                remaining -= coins[j];
                break;
            }
        }
    }
    return result;
}

    } int main() { vector coin = {1,5,10,25}; int amount = 47;

    cout<<"Dymanic Programming Approach Result: " <<endl;
vector<int> resultDP = coinChangeDP(coins,amount);
for(int i=0;i<resultDP.size();i++)
{
    cout<< resultDP[i]" ";
}
cout<<endl;
return 0;

    }

  • thinhproee
     + 0 comments
    /*
 * 2024 ^_^
 *ThinhNguyen97
 * 
 */

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;






public class Solve_problems 
{
    static int n;//so luong dong xu
    static int[] coins=new int[1001];//luu menh gia cac dong xu
    static long[] dp=new long[1000001];
    
    static long solve(int S)
    {
        dp[0]=1;//so tien la 0 tuc la co 1 cach lua chon
        
        for(int j=0;j<n;j++)//duyet het mang
            for(int i=coins[j];i<=S;i++)
            {
                dp[i]+=dp[i-coins[j]];
                //dp[i]%=1000000007;
            }
                
        
        return dp[S];
    }

    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(System.in);
        ////////
        int S=sc.nextInt();//so tien can tao ra
        n=sc.nextInt();
        for(int i=0;i<n;i++)
            coins[i]=sc.nextInt();
        System.out.println(solve(S));
        
        // Close the Scanner instance
        sc.close();
    }
}

  • erikw
     + 0 comments

    Simple Ruby DP solution:

    def make_change(n, coins)
  dp = Array.new(n + 1, 0)
  dp[0] = 1
  coins.each do |coin|
    (coin..n).each do |i|
      dp[i] += dp[i - coin]
    end
  end
  dp[n]
end

n, _m = gets.split.map(&:to_i)
coins = gets.split.map(&:to_i)
puts make_change(n, coins)

  • christopher_ott1
     + 0 comments

    Anyone know what change is needed to only return the number of odd solutions? Eg given the coins [1,2,5] and amount 5. The solutions are: [1,1,1,1,1] [2,111] [2,2,1] [5] There are four solutions, but only three odd solutions. I'm tearing my hair out trying to solve this.

    def make_change(coins, n): lookup = [1] + [0] * n coins_used_list = [] coins_used_counter = 0 for coin in coins: for amount in range(n+1-coin): lookup[amount+coin] += lookup[amount] return lookup[n]

    make_change(coins = [1,2,5], n = 5)

  • skizajurrahaman
     + 0 comments

    In c++ starter code, result is in int format and due to that I am getting WA in 3 test cases. Remember to change this if you are getting WA.