3 DP variants in C++

• ``````    int dp2(int amount, vector<int>& coins) {
int n = coins.size();
vector<vector<int>> dp(amount + 1, vector<int>(n + 1));
for(int j = 0; j <= n; ++j)
dp[0][j] = 1;
for(int i = 1; i <= amount; ++i) {
for(int j = 1; j <= n; ++j) {
//exclude jth coin and include jth coin(iff its more than current amount i)
dp[i][j] += (dp[i][j-1] + (i >= coins[j-1] ? dp[i - coins[j-1]][j] : 0));
}
}
return dp[amount][n];
}
int dp2b(int amount, vector<int>& coins) {
int n = coins.size();
vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
dp[0][0] = 1;
for(int i = 1; i <= n; ++i) {
dp[i][0] = 1;
for(int j = 1; j <= amount; ++j) {
dp[i][j] = dp[i-1][j] + (j >= coins[i-1] ? dp[i][j-coins[i-1]] : 0);
}
}
return dp[n][amount];
}
int dp1(int amount, vector<int>& coins) {
vector<int> dp(amount + 1);
dp[0] = 1;
for(auto coin : coins) {
for(int i = coin; i <= amount; ++i)
dp[i] += dp[i - coin];
}
return dp.back();
}
int change(int amount, vector<int>& coins) {
//return dp2(amount, coins);
//return dp2b(amount, coins);
return dp1(amount, coins);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.