Untitled
unknown
plain_text
2 years ago
887 B
7
Indexable
#include <iostream> #include <vector> using namespace std; int main() { // Citim valorile banilor si suma de platit int n, w; cin >> n >> w; vector<int> denominatiune(n+1); for (int i = 1; i <= n; i++) { cin >> denominatiune[i]; } // Initializam matricea dp cu valorile initiale vector<vector<int>> dp(n+1, vector<int>(w+1)); for (int i = 1; i <= n; i++) { dp[i][0] = 1; } // Calculam valorile dp for (int i = 1; i <= n; i++) { for (int j = 1; j <= w; j++) { if (j >= denominatiune[i]) { dp[i][j] = dp[i][j-denominatiune[i]] + dp[i-1][j]; } else { dp[i][j] = dp[i-1][j]; } } } // Afisam numarul de moduri in care se poate plati suma w cout << dp[n][w] << endl; return 0; }
Editor is loading...