CoderCharts:Coin Changes

gistfile1.java

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