karthiksai281
BAN USERpublic class Min_Coin_DP {
public static int Min_Coin(int []s,int sum)
{
int [] min_coins= new int[sum+1];
min_coins[0]=0;
for(int i=1;i<min_coins.length;i++)
min_coins[i]=Integer.MAX_VALUE;
for(int i=1;i<=sum;i++)
for(int j=0;j<s.length;j++)
if((s[j]<=i) && (min_coins[i-s[j]]+1<min_coins[i]))
min_coins[i]=min_coins[i-s[j]]+1;
return min_coins[sum];
}
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
int sum,n;
System.out.println("Enter the number of coins you have:");
n=in.nextInt();
int [] coins= new int[n];
System.out.println("\nEnter the coins you have:");
for(int i=0;i<n;i++)
coins[i]=in.nextInt();
System.out.println("\nEnter the Value to get change:");
sum=in.nextInt();
System.out.println("\nThe minimum number of coins required for a change of "+sum+" is :"+Min_Coin(coins,sum));
}
}
Every thing works fine except a small change.
- karthiksai281 October 24, 2012temp=s[x-1] because the strings are stored in an array.
What about the time complexity? This is the brute force way i guess..Is there any better way to achieve better time complexity?