We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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);
I have a question to others though, in java when I am trying to make it long I have to do a lot of casting, any other way to deal with the 'long' problem.
The Coin Change Problem
You are viewing a single comment's thread. Return to all comments →
public static long count(long sum,long[] coins , int 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);
I have a question to others though, in java when I am trying to make it long I have to do a lot of casting, any other way to deal with the 'long' problem.