Classic DP Problems

โจทย์ DP ที่พบบ่อยและวิธีแก้

Classic DP Problems

รวบรวมโจทย์ DP คลาสสิกที่พบบ่อยในการแข่งขัน

1. Knapsack Problem

0/1 Knapsack

มีของ n ชิ้น แต่ละชิ้นมี weight และ value เลือกของใส่กระเป๋าที่รับน้ำหนักได้ W ให้ได้ value สูงสุด (แต่ละชิ้นเลือกได้ครั้งเดียว)

// dp[i][w] = max value using items 0..i-1 with capacity w
int knapsack01(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i-1][w]; // ไม่เลือก item i
            
            if (weights[i-1] <= w) {
                dp[i][w] = max(dp[i][w], 
                    dp[i-1][w - weights[i-1]] + values[i-1]);
            }
        }
    }
    
    return dp[n][W];
}

// Space optimized O(W)
int knapsack01Optimized(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= weights[i]; w--) { // ต้องวนจากหลังไปหน้า
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    
    return dp[W];
}

Complexity: $O(nW)$

Unbounded Knapsack

เหมือน 0/1 Knapsack แต่เลือกแต่ละชิ้นได้ไม่จำกัด

int unboundedKnapsack(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<int> dp(W + 1, 0);
    
    for (int w = 0; w <= W; w++) {
        for (int i = 0; i < n; i++) {
            if (weights[i] <= w) {
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
    }
    
    return dp[W];
}

2. Coin Change

จำนวนเหรียญน้อยสุด

มีเหรียญหลายชนิด หาจำนวนเหรียญน้อยที่สุดที่รวมได้ target

int coinChange(vector<int>& coins, int target) {
    vector<int> dp(target + 1, INT_MAX);
    dp[0] = 0;
    
    for (int i = 1; i <= target; i++) {
        for (int c : coins) {
            if (c <= i && dp[i - c] != INT_MAX) {
                dp[i] = min(dp[i], dp[i - c] + 1);
            }
        }
    }
    
    return dp[target] == INT_MAX ? -1 : dp[target];
}

จำนวนวิธีทำเหรียญ

หาจำนวนวิธีที่จะรวมเหรียญได้ target

int coinChangeWays(vector<int>& coins, int target) {
    vector<int> dp(target + 1, 0);
    dp[0] = 1;
    
    for (int c : coins) {
        for (int i = c; i <= target; i++) {
            dp[i] += dp[i - c];
        }
    }
    
    return dp[target];
}

3. Longest Common Subsequence (LCS)

หา subsequence ที่ยาวที่สุดที่ปรากฏในทั้งสอง strings

string lcs(string& s1, string& s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // Fill DP table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    // Reconstruct LCS
    string lcsStr;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (s1[i-1] == s2[j-1]) {
            lcsStr += s1[i-1];
            i--; j--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }
    
    reverse(lcsStr.begin(), lcsStr.end());
    return lcsStr;
}

Complexity: $O(mn)$

4. Edit Distance (Levenshtein Distance)

หาจำนวน operations น้อยที่สุด (insert, delete, replace) เพื่อแปลง s1 เป็น s2

int editDistance(string& s1, string& s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    
    // Base cases
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } 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];
}

Complexity: $O(mn)$

5. Longest Increasing Subsequence (LIS)

หา subsequence ที่ยาวที่สุดที่เพิ่มขึ้นเรื่อยๆ

// O(n²) version
int lisBasic(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    
    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());
}

// O(n log n) version with binary search
int lisOptimized(vector<int>& nums) {
    vector<int> lis;
    
    for (int x : nums) {
        auto it = lower_bound(lis.begin(), lis.end(), x);
        if (it == lis.end()) {
            lis.push_back(x);
        } else {
            *it = x;
        }
    }
    
    return lis.size();
}

// Reconstruct actual LIS
vector<int> getLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> lis, parent(n), pos(n);
    
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(lis.begin(), lis.end(), nums[i]);
        int idx = it - lis.begin();
        
        if (it == lis.end()) {
            lis.push_back(nums[i]);
        } else {
            *it = nums[i];
        }
        
        pos[i] = idx;
        parent[i] = (idx == 0) ? -1 : pos[*find_if(
            nums.begin(), nums.begin() + i,
            [&](int x) { return x < nums[i]; }
        ) - nums.begin()];
    }
    
    // Backtrack to get actual LIS
    vector<int> result;
    int len = lis.size() - 1;
    for (int i = n - 1; i >= 0 && len >= 0; i--) {
        if (pos[i] == len) {
            result.push_back(nums[i]);
            len--;
        }
    }
    reverse(result.begin(), result.end());
    return result;
}

6. Longest Palindromic Subsequence

หา subsequence ที่ยาวที่สุดที่เป็น palindrome

int longestPalinSubseq(string& s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            
            if (s[i] == s[j]) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    
    return dp[0][n-1];
}

7. Partition Problem

ตรวจสอบว่าแบ่ง array ออกเป็น 2 กลุ่มที่มีผลรวมเท่ากันได้หรือไม่

bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 2 != 0) return false;
    
    int target = sum / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true;
    
    for (int num : nums) {
        for (int i = target; i >= num; i--) {
            dp[i] = dp[i] || dp[i - num];
        }
    }
    
    return dp[target];
}

8. Subset Sum

หาจำนวนวิธีเลือก subset ที่มีผลรวมเท่า target

int subsetSum(vector<int>& nums, int target) {
    vector<int> dp(target + 1, 0);
    dp[0] = 1;
    
    for (int num : nums) {
        for (int i = target; i >= num; i--) {
            dp[i] += dp[i - num];
        }
    }
    
    return dp[target];
}

9. Rod Cutting

ตัด rod ยาว n ให้ได้ราคาสูงสุด โดยราคาของ rod ยาว i คือ price[i]

int rodCutting(vector<int>& price, int n) {
    vector<int> dp(n + 1, 0);
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i] = max(dp[i], price[j-1] + dp[i - j]);
        }
    }
    
    return dp[n];
}

10. Egg Drop Problem

หาจำนวน drops น้อยที่สุดเพื่อหาชั้นที่ไข่แตก โดยมี k ไข่ และ n ชั้น

int eggDrop(int k, int n) {
    // dp[i][j] = max floors checkable with i eggs and j tries
    vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
    
    int tries = 0;
    while (dp[k][tries] < n) {
        tries++;
        for (int i = 1; i <= k; i++) {
            dp[i][tries] = dp[i-1][tries-1] + dp[i][tries-1] + 1;
        }
    }
    
    return tries;
}

สรุป

Problem	State	Complexity
0/1 Knapsack	`dp[i][w]`	$O(nW)$
Unbounded Knapsack	`dp[w]`	$O(nW)$
Coin Change	`dp[amount]`	$O(n \cdot target)$
LCS	`dp[i][j]`	$O(mn)$
Edit Distance	`dp[i][j]`	$O(mn)$
LIS	`dp[i]`	$O(n^2)$ or $O(n \log n)$
Subset Sum	`dp[target]`	$O(n \cdot target)$

💡 Tip: โจทย์ DP มักจะเป็นรูปแบบเดิมๆ ที่ดัดแปลง ฝึกทำโจทย์คลาสสิกให้คล่องก่อน