Untitled

coin chnanging Dynamic
import java.util.*;
public class coin_changing {
	public static int numberOfCoins(int arr[],int sum) {
		int answer=0;
		int n=arr.length;
		int coins[][]=new int[n][sum+1];
		for(int i=0;i<n;i++) {
			coins[i][0]=0;
		}
		for(int j=0;j<=sum;j++) {
			coins[0][j]=j;
		}
		for(int i=1;i<n;i++) {
			for(int j=1;j<=sum;j++) {
				if(arr[i]>j) {
					coins[i][j]=coins[i-1][j];
				}
				else {
				coins[i][j]=Math.min(coins[i-1][j],1+coins[i][j-arr[i]]);
				}
			}
		}
		answer=coins[n-1][sum];
		return answer;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		System.out.println("Enter length of coins Array: ");
		int n=sc.nextInt();
		int coinsArr[]=new int[n];
		System.out.println("Enter elemnts of coin array:");
		for(int i=0;i<n;i++) {
			coinsArr[i]=sc.nextInt();
		}
		System.out.println("Enter sum required:");
		int sum=sc.nextInt();
		int ans=numberOfCoins(coinsArr,sum);
		System.out.println("Minimum number of coins required to get sum     "+sum+" is "+ans);