Number Of Ways To Make Change
- Time : O(nd)
- Space : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include <vector>
using namespace std;
int numberOfWaysToMakeChange(int n, vector<int> denoms) {
vector<int> dp(n + 1, 0);
dp[0] = 1;
for(auto& denom : denoms) {
for(int i = denom; i <= n; i++) {
dp[i] += dp[i - denom];
}
}
return dp.back();
}
|
