spider68

coin change problem total way in o(n)space

May 16th, 2020
187
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.47 KB | None | 0 0
  1. long long numberOfWays(int coins[],int numberOfCoins,int value)
  2. {
  3.    
  4.     long long ways[value+1]={0};
  5.     ways[0]=1;
  6.     vector<int> coinsSet;
  7.    
  8.     for(int i=0;i<numberOfCoins;i++)
  9.     {
  10.         coinsSet.push_back(coins[i]);
  11.     }
  12.     for(auto coin:coinsSet)
  13.     {
  14.         for(int i=1;i<value+1;i++)
  15.         {
  16.             if(i>=coin)
  17.             {
  18.                 ways[i]=ways[i]+ways[i-coin];
  19.             }
  20.         }
  21.     }
  22.    
  23.     return ways[value];
  24. }
Add Comment
Please, Sign In to add comment