09. Dynamic Programming (Quy hoạch động)

🎯 Mục tiêu học tập

  • Hiểu khái niệm DP và overlapping subproblems
  • Phân biệt Top-down vs Bottom-up approach
  • Tối ưu hóa từ recursion sang DP
  • Giải quyết các bài toán DP kinh điển

📚 Lý thuyết

Dynamic Programming là gì?

Định nghĩa: Kỹ thuật giải quyết bài toán phức tạp bằng cách chia thành các subproblems đơn giản hơn.

Điều kiện áp dụng DP:

  1. Optimal Substructure: Lời giải tối ưu chứa lời giải tối ưu của subproblems
  2. Overlapping Subproblems: Các subproblems được tính toán lại nhiều lần

🎯 Approaches

1. Top-Down (Memoization)

// Recursion + Cache kết quả đã tính
int memo[];
int fibonacci(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fibonacci(n-1) + fibonacci(n-2);
}

2. Bottom-Up (Tabulation)

// Tính từ base case lên
int fibonacci(int n) {
    int[] dp = new int[n+1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

🧮 Bài toán kinh điển

1. Fibonacci Sequence

  • Naive: O(2^n)
  • DP: O(n)

2. Climbing Stairs

// n bậc thang, mỗi lần lên 1 hoặc 2 bậc
// Có bao nhiêu cách?
dp[i] = dp[i-1] + dp[i-2]

3. Coin Change

// Đổi tiền với số coin ít nhất
dp[amount] = min(dp[amount-coin] + 1) for all coins

4. Longest Common Subsequence (LCS)

// Tìm subsequence chung dài nhất của 2 string
if (s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + 1
else dp[i][j] = max(dp[i-1][j], dp[i][j-1])

5. 0/1 Knapsack

// Túi có trọng lượng W, n items có weight và value
// Tối đa hóa value
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

📊 Patterns phổ biến

1. Linear DP

  • Fibonacci, Climbing Stairs
  • State: dp[i] phụ thuộc dp[i-1], dp[i-2]...

2. 2D DP

  • LCS, Edit Distance, Knapsack
  • State: dp[i][j]

3. Tree DP

  • House Robber III, Binary Tree Maximum Path Sum
  • State phụ thuộc vào children

4. Bitmask DP

  • Traveling Salesman Problem
  • State bao gồm visited set

📋 Bài tập thực hành

Cơ bản:

  1. Fibonacci, Climbing Stairs
  2. Min Cost Climbing Stairs
  3. House Robber
  4. Maximum Subarray

Trung bình:

  1. Coin Change (2 variants)
  2. Longest Increasing Subsequence
  3. Unique Paths
  4. Edit Distance

Nâng cao:

  1. 0/1 Knapsack
  2. Longest Common Subsequence
  3. Palindrome Partitioning
  4. Regular Expression Matching

💡 Tips tối ưu

1. Space Optimization

// Thay vì 2D array, dùng 1D array nếu chỉ cần previous row

2. State Compression

// Với Fibonacci: chỉ cần 2 variables thay vì array

3. Identify Patterns

  • Có chọn lựa: dp[i] = max/min(option1, option2)
  • Counting: dp[i] = sum of ways
  • Existence: dp[i] = boolean

🚀 Chuẩn bị code

mkdir 09-dynamic-programming
# Files: BasicDP.java, ClassicProblems.java, DPPatterns.java, AdvancedDP.java