CareerCup

yep, the person above is right.

int coins( int[] coins, int amount ) {
	int[] table = new int[amount+1];

	Arrays.fill( table, Integer.MAX_VALUE - 100 );
	table[0] = 0;

	for ( int i = 1; i < table.length; i++ ) {
		for ( int j = 0; j < coins.length; j++ ) {
			if ( coins[j] <= i && 
                             table[i - coins[j]] + 1 < table[i] ) {
                            table[i] = table[i - coins[j]] + 1; 
                        }
                }
        }

        return table[amount];
}

No need for dynamic programming...simple greedy algorithm is sufficient...

yes greedy approach is best for this

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class Coins {
	Map<Integer, Integer> denoms = new HashMap<Integer, Integer>();
	List<Integer> d = new ArrayList<Integer>();
	public Coins() {
		denoms.put(10, 5);
		denoms.put(25, 5);
		denoms.put(1, 5);
		denoms.put(5, 5);
		
		d.add(1);
		d.add(5);
		d.add(10);
		d.add(25);
	}
	
	public int getCoins(int denom, int totalChange){
		int count=1;
		while(denom*++count <= totalChange){}
		return --count;
	}
	
	public void getChange(Map<Integer, Integer> change, int totalChange){
		
		if(totalChange <=0)return;
		
		//for the totalChange, get the nearest denom... 
		for(int i=d.size()-1; i>=0;i--){
			int aCoin = d.get(i);
			if(aCoin<=totalChange){
				int coins = getCoins(aCoin, totalChange);
				change.put(aCoin,coins);
				//.. Now how much more do we have left?
				int changeSoFar = aCoin * coins;
				int remChange = totalChange - changeSoFar;
				getChange(change, remChange);
				break;
			}
		}
		
	}
	
	public static void main(String[] args) {
		Coins c = new Coins();
		Map<Integer, Integer> chillar = new HashMap<Integer, Integer>();
		c.getChange(chillar, 92 );
		System.out.println(chillar);
	}
}

knapsack problem

import java.io.*;
import java.math.*;

public class Coins {
	static int[] a;
	public static void main(String[] args) throws Exception{
		int amount = 30;
		a = new int[amount+1];
		System.out.println( count( amount ) );
	}
	static int count( int amount ) {
		if (amount < 0) {
			return Integer.MAX_VALUE;
		} else if( amount == 0 ) {
			return 0;
		} else if( a[amount]>0 ) {
			return a[amount];
		} else {
			a[amount] = Math.min( count( amount-25 ), Math.min( count( amount-10 ), count( amount-1 ) ) ) + 1;
			return a[amount];
		}
	}
}

considering u have coins of 25, 10, and 1
Is this code correct ?

we can use dynamic programming to solve this problem, run time complexity should be
O(kN), where k = |denom| and N = amount, memory complexity is O(N)

Define f(i) = minimum number of coins needed to get amount of i
iterate j from 1 to amount
f(j) = 0 for j <= 0
f(j) = min{k in {denom}} ( j-k ) + 1; for j > 0

answer is f(amount)