Programare Dinamică C++ — Ghid Complet

Ce este Programarea Dinamică?

Programarea dinamică (DP) este o tehnică algoritmică care rezolvă probleme complexe prin descompunerea lor în subprobleme mai mici, stocând rezultatele intermediare pentru a evita recalcularea.

Principii cheie:

1. •Suprapunerea subproblemelor — aceeași subproblemă apare de mai multe ori
2. •Substructura optimă — soluția optimă se construiește din soluții optime ale subproblemelor

Abordări în Programarea Dinamică

1. Top-Down (Memoizare)

Copiază
1map<int, long long> memo;
2long long fibonacci(int n) {
3    if (n <= 1) return n;
4    if (memo.count(n)) return memo[n];
5    return memo[n] = fibonacci(n-1) + fibonacci(n-2);
6}

2. Bottom-Up (Tabulare)

Copiază
1long long fibonacci(int n) {
2    if (n <= 1) return n;
3    vector<long long> dp(n + 1);
4    dp[0] = 0; dp[1] = 1;
5    for (int i = 2; i <= n; i++)
6        dp[i] = dp[i-1] + dp[i-2];
7    return dp[n];
8}

Probleme Clasice de Programare Dinamică

1. Problema Rucsacului (Knapsack 0/1)

Copiază
1int knapsack(vector<int>& wt, vector<int>& val, int W, int n) {
2    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
3    for (int i = 1; i <= n; i++) {
4        for (int j = 0; j <= W; j++) {
5            dp[i][j] = dp[i-1][j];
6            if (j >= wt[i-1])
7                dp[i][j] = max(dp[i][j], dp[i-1][j-wt[i-1]] + val[i-1]);
8        }
9    }
10    return dp[n][W];
11}

2. Cel Mai Lung Subșir Comun (LCS)

Copiază
1int LCS(string s1, string s2) {
2    int m = s1.size(), n = s2.size();
3    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
4    for (int i = 1; i <= m; i++) {
5        for (int j = 1; j <= n; j++) {
6            if (s1[i-1] == s2[j-1])
7                dp[i][j] = dp[i-1][j-1] + 1;
8            else
9                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
10        }
11    }
12    return dp[m][n];
13}

3. Suma Maximă a unui Subvector (Kadane)

Copiază
1int maxSubarraySum(vector<int>& arr) {
2    int maxSum = arr[0], curSum = arr[0];
3    for (int i = 1; i < arr.size(); i++) {
4        curSum = max(arr[i], curSum + arr[i]);
5        maxSum = max(maxSum, curSum);
6    }
7    return maxSum;
8}

4. Cel Mai Lung Subșir Crescător (LIS)

Copiază
1int LIS(vector<int>& arr) {
2    int n = arr.size();
3    vector<int> dp(n, 1);
4    for (int i = 1; i < n; i++)
5        for (int j = 0; j < i; j++)
6            if (arr[j] < arr[i])
7                dp[i] = max(dp[i], dp[j] + 1);
8    return *max_element(dp.begin(), dp.end());
9}

5. Problema Monezilor (Coin Change)

Copiază
1int coinChange(vector<int>& coins, int amount) {
2    vector<int> dp(amount + 1, INT_MAX);
3    dp[0] = 0;
4    for (int i = 1; i <= amount; i++) {
5        for (int c : coins) {
6            if (c <= i && dp[i-c] != INT_MAX)
7                dp[i] = min(dp[i], dp[i-c] + 1);
8        }
9    }
10    return dp[amount] == INT_MAX ? -1 : dp[amount];
11}

Exerciții pentru Exersare

1. •Triunghi (dp pe triunghi de numere) — găsește suma maximă de la vârf la bază
2. •Edit Distance — numărul minim de operații pentru a transforma un string în altul
3. •Matrix Chain Multiplication — ordinea optimă de înmulțire a matricilor
4. •Egg Drop Problem — numărul minim de aruncări pentru a determina etajul critic

Programarea dinamică este un subiect esențial atât pentru BAC informatică, cât și pentru titularizare și olimpiadele de informatică.