You are viewing a single comment's thread. Return to all comments →
#include <vector> using namespace std; long long fun(int n, int i, vector<long> c, vector<vector<long long>> &dp) { if (i == 0) { return n % c[0] == 0; } if (dp[i][n] != 0) { return dp[i][n]; } long long take = 0; long long nottake = fun(n, i - 1, c, dp); if (c[i] <= n) { take = fun(n - c[i], i, c, dp); } return dp[i][n] = take + nottake; } long long getWays(int n, vector<long> c) { int l = c.size(); vector<vector<long long>> dp(l, vector<long long>(n + 1, 0)); return fun(n, l - 1, c, dp); }
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 →