Programare Dinamică în C++

Ce este Programarea Dinamică?

Programarea dinamică este o tehnică de optimizare care rezolvă probleme complexe prin:

1. •Descompunere în subprobleme mai mici
2. •Memorare (memoization) a rezultatelor subproblemelor
3. •Combinare a soluțiilor subproblemelor

Fibonacci - Exemplu Clasic

Varianta Naivă (ineficientă)

Copiază
1// O(2^n) - foarte lent
2int fibNaiv(int n) {
3    if (n <= 1) return n;
4    return fibNaiv(n - 1) + fibNaiv(n - 2);
5}

Cu Programare Dinamică (Top-Down / Memoization)

Copiază
1#include <vector>
2using namespace std;
3
4vector<long long> memo(100, -1);
5
6long long fibMemo(int n) {
7    if (n <= 1) return n;
8    if (memo[n] != -1) return memo[n];
9    return memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
10}

Cu Programare Dinamică (Bottom-Up)

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

Problema Subșirului Crescător Maximal (LIS)

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

Când folosim Programare Dinamică?

1. •Subprobleme suprapuse - aceleași subprobleme se rezolvă de mai multe ori
2. •Substructură optimă - soluția optimă conține soluții optime ale subproblemelor