Dynamic Programming — Quy hoạch động

Khi nào dùng DP?

DP áp dụng khi bài toán có 2 tính chất:

1. Overlapping Subproblems — cùng bài toán con được giải nhiều lần
2. Optimal Substructure — lời giải tối ưu chứa lời giải tối ưu của bài con

Fibonacci — DP đầu tiên

// Brute force: O(2^n) — exponential
public int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2); // tính lại nhiều lần!
}

// Top-down (Memoization): O(n)
public int fibMemo(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

// Bottom-up (Tabulation): O(n), O(1) space
public int fibDP(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Framework giải DP

1. Define state — dp[i] nghĩa là gì?
2. Transition — dp[i] được tính từ dp nào?
3. Base case — dp[0], dp[1] bằng bao nhiêu?
4. Answer — kết quả ở dp nào?

Key insight: DP không khó ở code — khó ở việc define state đúng. Khi state đúng, transition tự nhiên hiện ra.