Skip to content

Instantly share code, notes, and snippets.

@bknarendra
Created May 14, 2012 07:45
Show Gist options
  • Save bknarendra/2692522 to your computer and use it in GitHub Desktop.
Save bknarendra/2692522 to your computer and use it in GitHub Desktop.
CoderCharts:Coin Changes
import java.util.*;
import java.io.*;
public class coin_changes
{
public static void main (String[] args) throws Exception
{
int max=-1,i,j;
Scanner sc=new Scanner(new File(args[0]));
Vector <Integer>v=new Vector<Integer>();
while(sc.hasNext())
{
i=sc.nextInt();
if(i>max) max=i;
v.add(i);
}
int a[]={1,5,10,25};
int dp[][]=new int[max+1][4];
dp[0][0]=1;
for(i=0;i<4;i++) dp[0][i]=1;
for(i=1;i<=max;i++)
for(j=0;j<4;j++)
dp[i][j]=(((j-1)<0)?0:dp[i][j-1])+((i-a[j])<0?0:((i-a[j]==0)?1:dp[i-a[j]][j]));
for(i=0;i<v.size();i++)
System.out.println(dp[new Integer(v.elementAt(i)).intValue()][3]);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment