Dynamic Programming Fundamentals

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Top-down Fibonacci with memoization
5
long long fibMemo(int n, vector<long long>& memo) {
6
    if (n <= 1) return n;                 // base cases: F(0)=0, F(1)=1
7
    if (memo[n] != -1) return memo[n];    // reuse cached result
8
    // Recurrence: F(n) = F(n-1) + F(n-2)
9
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
10
    return memo[n];
11
}
12
13
// Bottom-up Fibonacci with tabulation
14
long long fibTab(int n) {
15
    if (n <= 1) return n;
16
    long long prev2 = 0; // F(0)
17
    long long prev1 = 1; // F(1)
18
    for (int i = 2; i <= n; ++i) {
19
        long long cur = prev1 + prev2;   // transition
20
        prev2 = prev1;                   // shift window
21
        prev1 = cur;
22
    }
23
    return prev1;
24
}
25
26
int main() {
27
    ios::sync_with_stdio(false);
28
    cin.tie(nullptr);
29
30
    int n = 45; // Example input; large enough to see benefits over naive recursion
31
32
    vector<long long> memo(n + 1, -1);
33
    cout << "Top-Down (memo) F(" << n << ") = " << fibMemo(n, memo) << "\n";
34
35
    cout << "Bottom-Up (tab) F(" << n << ") = " << fibTab(n) << "\n";
36
37
    return 0;
38
}
39

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Returns pair<maxValue, chosenIndices>
5
pair<int, vector<int>> knapsack01(const vector<int>& w, const vector<int>& v, int W) {
6
    int n = (int)w.size();
7
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
8
9
    // Build table: dp[i][cap] = best value using first i items with capacity cap
10
    for (int i = 1; i <= n; ++i) {
11
        for (int cap = 0; cap <= W; ++cap) {
12
            dp[i][cap] = dp[i - 1][cap]; // skip item i-1 by default
13
            if (w[i - 1] <= cap) {
14
                dp[i][cap] = max(dp[i][cap], dp[i - 1][cap - w[i - 1]] + v[i - 1]);
15
            }
16
        }
17
    }
18
19
    // Reconstruction: walk backwards to find which items were taken
20
    vector<int> chosen;
21
    int cap = W;
22
    for (int i = n; i >= 1; --i) {
23
        if (dp[i][cap] != dp[i - 1][cap]) {           // value improved by taking item i-1
24
            chosen.push_back(i - 1);
25
            cap -= w[i - 1];                          // reduce capacity by item's weight
26
        }
27
    }
28
    reverse(chosen.begin(), chosen.end());
29
    return {dp[n][W], chosen};
30
}
31
32
int main() {
33
    ios::sync_with_stdio(false);
34
    cin.tie(nullptr);
35
36
    // Example: 4 items
37
    vector<int> w = {3, 4, 7, 8};
38
    vector<int> v = {4, 5, 10, 11};
39
    int W = 10;
40
41
    auto [best, items] = knapsack01(w, v, W);
42
    cout << "Best value = " << best << "\nItems taken (0-indexed): ";
43
    for (int idx : items) cout << idx << ' ';
44
    cout << "\n";
45
    return 0;
46
}
47

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// O(n^2) LIS DP with path reconstruction
5
pair<int, vector<int>> LIS(const vector<int>& a) {
6
    int n = (int)a.size();
7
    vector<int> dp(n, 1);       // dp[i] = LIS length ending at i
8
    vector<int> parent(n, -1);  // parent[i] = previous index in LIS ending at i
9
10
    int bestLen = 0, bestEnd = -1;
11
    for (int i = 0; i < n; ++i) {
12
        for (int j = 0; j < i; ++j) {
13
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
14
                dp[i] = dp[j] + 1;
15
                parent[i] = j;
16
            }
17
        }
18
        if (dp[i] > bestLen) {
19
            bestLen = dp[i];
20
            bestEnd = i;
21
        }
22
    }
23
24
    // Reconstruct sequence by following parent pointers
25
    vector<int> seq;
26
    for (int cur = bestEnd; cur != -1; cur = parent[cur]) seq.push_back(a[cur]);
27
    reverse(seq.begin(), seq.end());
28
    return {bestLen, seq};
29
}
30
31
int main() {
32
    ios::sync_with_stdio(false);
33
    cin.tie(nullptr);
34
35
    vector<int> a = {10, 9, 2, 5, 3, 7, 101, 18};
36
    auto [len, seq] = LIS(a);
37
    cout << "LIS length = " << len << "\nSequence: ";
38
    for (int x : seq) cout << x << ' ';
39
    cout << "\n";
40
    return 0;
41
}
42

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int editDistance(const string& s, const string& t) {
5
    int n = (int)s.size();
6
    int m = (int)t.size();
7
    // Use two rows to reduce space from O(nm) to O(m)
8
    vector<int> prev(m + 1), cur(m + 1);
9
10
    // Base: dp[0][j] = j (insert j chars), dp[i][0] = i (delete i chars)
11
    iota(prev.begin(), prev.end(), 0); // prev[j] = j for i = 0
12
13
    for (int i = 1; i <= n; ++i) {
14
        cur[0] = i; // converting s[0..i-1] to empty requires i deletions
15
        for (int j = 1; j <= m; ++j) {
16
            int cost = (s[i - 1] == t[j - 1]) ? 0 : 1; // substitution cost
17
            cur[j] = min({
18
                prev[j] + 1,        // delete s[i-1]
19
                cur[j - 1] + 1,     // insert t[j-1]
20
                prev[j - 1] + cost  // match/substitute
21
            });
22
        }
23
        swap(prev, cur);
24
    }
25
    return prev[m];
26
}
27
28
int main() {
29
    ios::sync_with_stdio(false);
30
    cin.tie(nullptr);
31
32
    string s = "kitten", t = "sitting";
33
    cout << "Edit distance between '" << s << "' and '" << t << "' = " << editDistance(s, t) << "\n";
34
    return 0;
35
}
36