🧩 Quy hoạch động (Dynamic Programming)
📖 Giới thiệu
Dynamic Programming (DP) là một trong những kỹ thuật optimization mạnh mẽ nhất trong computer science, giải quyết các vấn đề phức tạp bằng cách chia nhỏ thành subproblems đơn giản hơn và tái sử dụng solutions đã tính toán. DP là core technique trong competitive programming và real-world optimization.
Khi nào sử dụng DP?
- Optimal Substructure: Solution tối ưu được build từ optimal solutions của subproblems
- Overlapping Subproblems: Các subproblems được tính toán lặp lại nhiều lần
- Optimization Problems: Tìm min/max value thỏa mãn constraints
Two main approaches:
- Memoization (Top-down): Recursive với caching
- Tabulation (Bottom-up): Iterative với table building
Real-world applications:
- Route optimization: GPS shortest path
- Resource allocation: Knapsack variants
- String algorithms: Edit distance, LCS
- Financial modeling: Portfolio optimization
- Game theory: Optimal strategy calculation
🔧 Cú pháp
Classic DP Problems
cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
// Fibonacci - Introduction to DP
class FibonacciDP {
public:
// Naive recursive - O(2^n)
long long fibRecursive(int n) {
if (n <= 1) return n;
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
// Memoization approach - O(n)
long long fibMemo(int n, vector<long long>& memo) {
if (n <= 1) return n;
if (memo[n] != -1) {
return memo[n];
}
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
// Tabulation approach - O(n)
long long fibTabulation(int n) {
if (n <= 1) return n;
vector<long long> dp(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];
}
// Space-optimized - O(1)
long long fibOptimized(int n) {
if (n <= 1) return n;
long long prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; i++) {
long long current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
};
// 0/1 Knapsack Problem
class KnapsackDP {
public:
// Recursive with memoization
int knapsackMemo(vector<int>& weights, vector<int>& values, int capacity,
int n, vector<vector<int>>& memo) {
if (n == 0 || capacity == 0) {
return 0;
}
if (memo[n][capacity] != -1) {
return memo[n][capacity];
}
// If weight of nth item is more than capacity, exclude it
if (weights[n - 1] > capacity) {
memo[n][capacity] = knapsackMemo(weights, values, capacity, n - 1, memo);
} else {
// Return max of including or excluding the item
int include = values[n - 1] + knapsackMemo(weights, values,
capacity - weights[n - 1], n - 1, memo);
int exclude = knapsackMemo(weights, values, capacity, n - 1, memo);
memo[n][capacity] = max(include, exclude);
}
return memo[n][capacity];
}
// Tabulation approach
int knapsackTabulation(vector<int>& weights, vector<int>& values, int capacity) {
int n = weights.size();
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = max(dp[i - 1][w], // Exclude item
dp[i - 1][w - weights[i - 1]] + values[i - 1]); // Include item
} else {
dp[i][w] = dp[i - 1][w]; // Exclude item
}
}
}
return dp[n][capacity];
}
// Space-optimized version
int knapsackOptimized(vector<int>& weights, vector<int>& values, int capacity) {
int n = weights.size();
vector<int> dp(capacity + 1, 0);
for (int i = 0; i < n; i++) {
// Traverse in reverse to avoid using updated values
for (int w = capacity; w >= weights[i]; w--) {
dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
};
// Longest Increasing Subsequence (LIS)
class LongestIncreasingSubsequence {
public:
// DP approach - O(n²)
int lisDP(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1); // dp[i] = length of LIS ending at i
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
// Binary search approach - O(n log n)
int lisBinarySearch(vector<int>& nums) {
vector<int> tails; // tails[i] = smallest ending element of LIS of length i+1
for (int num : nums) {
auto it = lower_bound(tails.begin(), tails.end(), num);
if (it == tails.end()) {
tails.push_back(num);
} else {
*it = num;
}
}
return tails.size();
}
// Get actual LIS sequence
vector<int> getLISSequence(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
vector<int> parent(n, -1);
int maxLength = 1;
int maxIndex = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
parent[i] = j;
}
}
if (dp[i] > maxLength) {
maxLength = dp[i];
maxIndex = i;
}
}
// Reconstruct sequence
vector<int> lis;
int current = maxIndex;
while (current != -1) {
lis.push_back(nums[current]);
current = parent[current];
}
reverse(lis.begin(), lis.end());
return lis;
}
};Advanced DP Patterns
cpp
// Edit Distance (Levenshtein Distance)
int editDistance(string word1, string word2) {
int m = word1.length(), n = word2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
// Initialize base cases
for (int i = 0; i <= m; i++) dp[i][0] = i; // Delete all characters
for (int j = 0; j <= n; j++) dp[0][j] = j; // Insert all characters
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1]; // No operation needed
} else {
dp[i][j] = 1 + min({
dp[i - 1][j], // Delete
dp[i][j - 1], // Insert
dp[i - 1][j - 1] // Replace
});
}
}
}
return dp[m][n];
}
// Longest Common Subsequence (LCS)
int longestCommonSubsequence(string text1, string text2) {
int m = text1.length(), n = text2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
// Coin Change Problem
class CoinChange {
public:
// Minimum coins needed
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i && dp[i - coin] != INT_MAX) {
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
// Number of ways to make amount
int coinChangeWays(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
};
// House Robber Problem
int rob(vector<int>& nums) {
if (nums.empty()) return 0;
if (nums.size() == 1) return nums[0];
int prev2 = 0, prev1 = 0;
for (int num : nums) {
int current = max(prev1, prev2 + num);
prev2 = prev1;
prev1 = current;
}
return prev1;
}
// House Robber II (Circular)
int robCircular(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
auto robRange = [](vector<int>& nums, int start, int end) {
int prev2 = 0, prev1 = 0;
for (int i = start; i <= end; i++) {
int current = max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = current;
}
return prev1;
};
// Either rob first house (can't rob last) or rob last house (can't rob first)
return max(robRange(nums, 0, nums.size() - 2),
robRange(nums, 1, nums.size() - 1));
}🔬 Phân tích & Giải thích chi tiết
DP vs Recursion vs Greedy
Dynamic Programming:
- Optimal substructure + Overlapping subproblems
- Guarantees optimal solution
- Time complexity: Usually O(n²) or O(n³)
- Examples: Knapsack, LCS, Edit Distance
Greedy:
- Makes locally optimal choices
- May not guarantee global optimum
- Time complexity: Usually O(n log n)
- Examples: Activity selection, Huffman coding
Recursion:
- Solves subproblems multiple times
- Exponential time without memoization
- Natural for problems with recursive structure
- Examples: Tree traversal, combinatorics
Space Optimization Techniques
cpp
// 2D DP can often be optimized to 1D
// Example: Knapsack space optimization
// Original 2D version
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1));
// Optimized 1D version (only need previous row)
vector<int> dp(capacity + 1);
// For some problems, only need O(1) space
// Example: Fibonacci
int prev2 = 0, prev1 = 1; // Only need last two valuesState Design Principles
Good State Definition:
- Complete: Captures all necessary information
- Minimal: No redundant information
- Efficient: Easy to compute and store
Common State Patterns:
dp[i]- Using first i elementsdp[i][j]- 2D grid or two sequencesdp[i][j][k]- 3D state with additional constraint
💻 Ví dụ minh họa
Ví dụ 1: Comprehensive DP Problem Solver
cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <chrono>
using namespace std;
class DynamicProgrammingSolver {
public:
// Maximum Subarray Sum (Kadane's Algorithm)
int maxSubarraySum(vector<int>& nums) {
int maxSum = nums[0];
int currentSum = nums[0];
for (int i = 1; i < nums.size(); i++) {
currentSum = max(nums[i], currentSum + nums[i]);
maxSum = max(maxSum, currentSum);
}
return maxSum;
}
// Unique Paths in Grid
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 1));
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
// Unique Paths with Obstacles
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
if (obstacleGrid[0][0] == 1) return 0;
vector<vector<int>> dp(m, vector<int>(n, 0));
dp[0][0] = 1;
// Initialize first row
for (int j = 1; j < n; j++) {
dp[0][j] = (obstacleGrid[0][j] == 0) ? dp[0][j - 1] : 0;
}
// Initialize first column
for (int i = 1; i < m; i++) {
dp[i][0] = (obstacleGrid[i][0] == 0) ? dp[i - 1][0] : 0;
}
// Fill the rest
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 0) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
// Minimum Path Sum
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n));
dp[0][0] = grid[0][0];
// First row
for (int j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// First column
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// Fill the rest
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
// Word Break II - All possible sentences
vector<string> wordBreakII(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
unordered_map<string, vector<string>> memo;
return wordBreakHelper(s, wordSet, memo);
}
private:
vector<string> wordBreakHelper(string s, unordered_set<string>& wordSet,
unordered_map<string, vector<string>>& memo) {
if (memo.find(s) != memo.end()) {
return memo[s];
}
vector<string> result;
if (wordSet.find(s) != wordSet.end()) {
result.push_back(s);
}
for (int i = 1; i < s.length(); i++) {
string prefix = s.substr(0, i);
if (wordSet.find(prefix) != wordSet.end()) {
vector<string> suffixes = wordBreakHelper(s.substr(i), wordSet, memo);
for (string suffix : suffixes) {
result.push_back(prefix + " " + suffix);
}
}
}
memo[s] = result;
return result;
}
public:
void demonstrateDP() {
cout << "=== DYNAMIC PROGRAMMING DEMONSTRATIONS ===" << endl;
// Max Subarray Sum
vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
cout << "\n📊 Maximum Subarray Sum:" << endl;
cout << "Array: ";
for (int num : nums) cout << num << " ";
cout << "\nMax sum: " << maxSubarraySum(nums) << endl;
// Unique Paths
cout << "\n🔢 Unique Paths in 3x7 grid: " << uniquePaths(3, 7) << endl;
// Min Path Sum
vector<vector<int>> grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
cout << "\n🗺️ Minimum Path Sum:" << endl;
cout << "Grid:" << endl;
for (auto& row : grid) {
for (int val : row) cout << val << " ";
cout << endl;
}
cout << "Min path sum: " << minPathSum(grid) << endl;
// Word Break II
string s = "catsanddog";
vector<string> wordDict = {"cat", "cats", "and", "sand", "dog"};
cout << "\n📝 Word Break II:" << endl;
cout << "String: " << s << endl;
cout << "Dictionary: ";
for (string word : wordDict) cout << word << " ";
cout << endl;
vector<string> sentences = wordBreakII(s, wordDict);
cout << "Possible sentences:" << endl;
for (string sentence : sentences) {
cout << "\"" << sentence << "\"" << endl;
}
}
};
int main() {
DynamicProgrammingSolver solver;
solver.demonstrateDP();
return 0;
}🏋️ Thực hành
Bài tập 1: Stock Trading Problems
Implement various stock trading DP problems:
- Best time to buy and sell stock (one transaction)
- Multiple transactions allowed
- With transaction fee
- With cooldown period
Bài tập 2: Palindrome Problems
Solve palindrome-related DP problems:
- Longest palindromic substring
- Palindrome partitioning (minimum cuts)
- Count of palindromic substrings
Bài tập 3: Matrix Chain Multiplication
Find optimal way to multiply chain of matrices:
- Minimize scalar multiplications
- Use interval DP approach
- Print optimal parenthesization
Bài tập 4: Advanced Knapsack Variants
Implement knapsack variations:
- Unbounded knapsack (unlimited items)
- Multiple knapsack (multiple containers)
- 2D knapsack (weight + volume constraints)
📋 Tóm tắt
Các điểm quan trọng
DP Requirements:
- Optimal Substructure: Optimal solution contains optimal solutions of subproblems
- Overlapping Subproblems: Subproblems are solved multiple times
Common Patterns:
- Linear DP: dp[i] depends on dp[i-1], dp[i-2], etc.
- Grid DP: 2D problems, path counting
- Interval DP: Problems on ranges/intervals
- Tree DP: DP on tree structures
Optimization Techniques:
- Space optimization: Reduce 2D to 1D when possible
- Memoization: Cache results to avoid recomputation
- Bottom-up vs Top-down: Choose based on problem structure
Best Practices
Problem Analysis:
- Identify if problem has optimal substructure
- Check for overlapping subproblems
- Define state clearly and minimally
- Consider space-time tradeoffs
Implementation:
- Start with recursive solution
- Add memoization for top-down DP
- Convert to tabulation for bottom-up DP
- Optimize space if possible
Chuẩn bị cho bài tiếp theo
Bài học tiếp theo sẽ tìm hiểu về Graph Algorithms:
- Graph Representation: Adjacency list, matrix
- Traversal: DFS, BFS applications
- Shortest Path: Dijkstra, Bellman-Ford
- Minimum Spanning Tree: Kruskal, Prim
- Advanced: Topological sort, strongly connected components
Dynamic Programming là powerful technique cho optimization problems. Master DP patterns để solve complex algorithmic challenges efficiently!