Flashcards
Coin change- total ways
Cards in this deck (1)
- 1For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5. https://www.youtube.com/watch?v=_fgjrs570YEstatic long countWays(int S[], int m, int n)
{
//Time complexity of this function: O(mn)
//Space Complexity of this function: O(n)
// table[i] will be storing the number of solutions
// for value i. We need n+1 rows as the table is
// constructed in bottom up manner using the base
// case (n = 0)
long[] table = new long[n+1];
// Initialize all table values as 0
Arrays.fill(table, 0); //O(n)
// Base case (If given value is 0)
table[0] = 1;
// Pick all coins one by one and update the table[]
// values after the index greater than or equal to
// the value of the picked coin
for (int i=0; i
Information
- Description
- Flashcards on Coin change- total ways, created by Suhas S on 28/05/2018.
- Created by
- Suhas S
- Views
- 0
- Rating