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.
This is my solution in Java language, based on the Internet.
publicstaticlonggetWays(intn,List<Long>c){// Write your code here/* Time: O(n * c) Space: O(n * c) Thanks to: youtuber Back To Back SWE */ints=c.size();long[][]ways=newlong[s+1][n+1];//This matrix has each row i represent for first ith elements in c be used//This matrix has each column j represent for subproblem j //When change for 0 for(inti=0;i<=s;i++){ways[i][0]=1;}//When there is no coin to changefor(inti=1;i<=n;i++){ways[0][i]=0;}//Calculate every subproblems before calculate the main solution//Each subproblem represent the amount of unique ways to solve./*A problem can be divide into 2 separate cases: + When we just use first (i-1)th elements in c + When we use first ith elements in c for subproblem (j - coin) with coin is the value of ith elements in c */for(inti=1;i<=s;i++){for(intj=1;j<=n;j++){ways[i][j]=ways[i-1][j];intx=j-(int)(long)c.get(i-1);if(x>=0)ways[i][j]+=ways[i][x];}}returnways[s][n];}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
The Coin Change Problem
You are viewing a single comment's thread. Return to all comments →
This is my solution in Java language, based on the Internet.