Dynamic Programming 09

Given a value N, find the number of ways to make change for N cents, if we have infinite supply of each of S = { S1, S2, .. , SM } valued coins.

Problem link :- click here

Code

import java.util.Arrays;
import java.util.Scanner;

public class DynamicProgramming_09
{
	static int coinChange(int[] coins, int n, int sum)
	{
		if(sum == 0)
			return 1;
		
		if(n == 0)
			return 0;
		
		if(sum < 0)
			return 0;
		
		if(sum>0 && n<=0)
			return 0;
		
		return coinChange(coins, n-1, sum) + coinChange(coins, n, sum-coins[n-1]);
	}
	
	static int coinChange1(int[] coins,int n, int sum)
	{
		int noWaysOfSum[] = new int[sum+1];
		
		Arrays.fill(noWaysOfSum, 0);
		
		noWaysOfSum[0] = 1;
		
		for(int i=0; i<n; i++)			//For each coin
		{
			//j ---> will have all the value of sum, in which coin coins[i] can contribute to sum.
			for(int j=coins[i]; j<=sum; j++)
			{
				noWaysOfSum[j] += noWaysOfSum[j - coins[i]];
			}
		}
		
		for(int x: noWaysOfSum)
			System.out.print(x + "\t");
		
		return noWaysOfSum[sum];
	}

	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		
		System.out.print("Enter the number of coins : ");
		int n = s.nextInt();
		int coins[] = new int[n];
		
		System.out.println("Enter the value of coins : ");
		for(int i=0; i<n; i++)
			coins[i] = s.nextInt();
		
		System.out.print("Enter the sum value : ");
		int sum = s.nextInt();
		
		int ans = coinChange1(coins, n, sum);
		System.out.println("\n\n" + ans);
		
		s.close();
	}

}