Help for top down dp

#1

i am not able to write top down dp
please help;

public static void main(String args[]) {

Scanner sc=new Scanner(System.in);

		int total=sc.nextInt();

		int n=sc.nextInt();

		int coins[]=new int[n];

		int min=Integer.MAX_VALUE;

        int max=Integer.MIN_VALUE;

		for(int i=0;i<n;i++){

		coins[i]=sc.nextInt();

		 max=Math.max(max,coins[i]);

		 min=Math.min(min,coins[i]);

		}

    

         System.out.println(f(total,coins.length-1,coins));
    }

    static int f(int total,int i,int[] coins){

        if(total<0)

            return 0;

        if(total==0)

            return 1;

        if(i<0)

            return 0;
        
       
        return f(total-coins[i],i,coins)+f(total,i-1,coins);
}

}

#2

Hello @S18CRX0174,

  1. Always share your code using Online Coding Blocks IDE.

  2. Coming back to your doubt:
    public static long count(long sum,long[] coins , int coin_num){

    if(sum==0){

    return 1;

} 
 else if(sum<0){
     return 0;
 }
 else if(coin_num<=0){
     return 0;
 }
 else if(memo[(int)sum][coin_num]!=-1){
      return memo[(int)sum][coin_num];
}

 else{
 memo[(int)sum][coin_num]=count(sum,coins,coin_num-1)+count(sum-coins[coin_num-1],coins,coin_num);
return memo[(int)sum][coin_num];

    }
    }

    Here we are caching the previous result in memo multidimensional array. First you need to initialize it wih some number(you can use Arrays.fill for that) Also I tried to make it clear what memo is really doing. Means if the ways for particular sum is already there then no need to calulate again. Else go ahead and solve.

    sum = amount

    coins = array of all available coins.

    coin_num is length of coins array(or you can say that next int in first line of this question’s input)

    So basically if you have

    sum = 100;

    coins[] = {25,10,5,1};

    coin_num = 4;

    memo[][] = new long[sum+1][coin_num+1];

    and then call countWays(sum,coins,coin_num);

Hope, this would help.
Give a like if you are satisfied.

#3

thanks for your help

#4

vaise kon se year me ho and colleng kon sa hai

#5

Hii @S18CRX0174,

I m in fourth year and from MAIT.