ICPC Competitive Programming
← กลับหน้าหลัก

พื้นฐาน Dynamic Programming

แนวคิดและเทคนิคพื้นฐานของ Dynamic Programming

พื้นฐาน Dynamic Programming

Dynamic Programming (DP) เป็นเทคนิคการแก้ปัญหาโดยการแบ่งปัญหาใหญ่ออกเป็นปัญหาย่อย แล้วเก็บคำตอบไว้ใช้ซ้ำ

แนวคิดหลัก

1. Optimal Substructure

คำตอบของปัญหาใหญ่สร้างจากคำตอบของปัญหาย่อย

2. Overlapping Subproblems

ปัญหาย่อยถูกแก้ซ้ำหลายครั้ง → เก็บคำตอบไว้ใช้ซ้ำ

ตัวอย่าง: Fibonacci

วิธี Recursive (ไม่มี DP) - ช้ามาก

// O(2^n) - Exponential
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

วิธี Top-Down (Memoization)

vector<int> memo(n + 1, -1);

// O(n)
int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n]; // ใช้ค่าที่เคยคำนวณไว้
    
    return memo[n] = fib(n - 1) + fib(n - 2);
}

วิธี Bottom-Up (Tabulation)

// O(n)
int fib(int n) {
    if (n <= 1) return n;
    
    vector<int> 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)
int fibOptimized(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;
}

ขั้นตอนการแก้ปัญหา DP

  1. Define State: กำหนดว่า dp[i] หมายถึงอะไร
  2. Base Case: กำหนดค่าเริ่มต้น
  3. Transition: หาความสัมพันธ์ระหว่าง states
  4. Answer: คำตอบอยู่ที่ state ไหน
  5. Order of Computation: คำนวณ state ไหนก่อน

รูปแบบ DP ที่พบบ่อย

1. Linear DP

State เป็น 1 มิติ คำนวณจาก states ก่อนหน้า

// ตัวอย่าง: Maximum subarray sum (Kadane's)
int maxSubarray(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n); // dp[i] = max sum ending at i
    
    dp[0] = nums[0];
    int ans = dp[0];
    
    for (int i = 1; i < n; i++) {
        dp[i] = max(nums[i], dp[i-1] + nums[i]);
        ans = max(ans, dp[i]);
    }
    
    return ans;
}

2. 2D DP

State เป็น 2 มิติ

// ตัวอย่าง: Grid path count
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];
}

3. DP on Subsequences

เกี่ยวกับ subsequence ของ array/string

// ตัวอย่าง: Longest Increasing Subsequence (LIS)
// dp[i] = length of LIS ending at index i

int lis(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 using 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();
}

4. DP on Strings

// ตัวอย่าง: Longest Common Subsequence (LCS)
// dp[i][j] = LCS of s1[0..i-1] and s2[0..j-1]

int lcs(string& s1, string& s2) {
    int m = s1.size(), n = s2.size();
    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 (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]);
            }
        }
    }
    
    return dp[m][n];
}

5. Interval DP

DP บน interval [i, j]

// ตัวอย่าง: Matrix Chain Multiplication
// dp[i][j] = minimum cost to multiply matrices i to j

int matrixChain(vector<int>& dims) {
    int n = dims.size() - 1; // number of matrices
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k+1][j] + 
                           dims[i] * dims[k+1] * dims[j+1];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    
    return dp[0][n-1];
}

6. Bitmask DP

ใช้ bitmask แทน state ของ subset

// ตัวอย่าง: Traveling Salesman Problem (TSP)
// dp[mask][i] = min cost to visit cities in mask, ending at city i

int tsp(vector<vector<int>>& dist) {
    int n = dist.size();
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    
    dp[1][0] = 0; // start at city 0
    
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int last = 0; last < n; last++) {
            if (!(mask & (1 << last))) continue;
            if (dp[mask][last] == INF) continue;
            
            for (int next = 0; next < n; next++) {
                if (mask & (1 << next)) continue;
                
                int newMask = mask | (1 << next);
                dp[newMask][next] = min(dp[newMask][next],
                                        dp[mask][last] + dist[last][next]);
            }
        }
    }
    
    // Return to start
    int fullMask = (1 << n) - 1;
    int ans = INF;
    for (int i = 0; i < n; i++) {
        ans = min(ans, dp[fullMask][i] + dist[i][0]);
    }
    
    return ans;
}

เทคนิคการ Optimize DP

1. Space Optimization

ถ้า current state ขึ้นกับแค่ 1-2 states ก่อนหน้า ใช้ตัวแปรแทน array

// แทนที่จะใช้ dp[n]
// ใช้แค่ prev และ curr

2. Prefix Sum

ถ้าต้อง sum ช่วง ให้ precompute prefix sum

3. Binary Search Optimization

บาง DP สามารถใช้ binary search ลด complexity (เช่น LIS)

4. Monotonic Queue/Stack

สำหรับ sliding window maximum/minimum

เคล็ดลับ

  1. เริ่มจากตัวอย่างเล็กๆ - ลองทำมือกับ input ขนาดเล็กก่อน
  2. กำหนด state ให้ชัด - เขียนว่า dp[i] หมายถึงอะไร
  3. หา recurrence - ความสัมพันธ์ระหว่าง states
  4. ระวัง base case - ค่าเริ่มต้นผิดทำให้ผิดทั้งหมด
  5. ดู complexity - ต้องเร็วพอสำหรับ constraints

สรุป DP Patterns

PatternStateExample
Lineardp[i]Fibonacci, Max Subarray
2D Griddp[i][j]Path Count, Edit Distance
Subsequencedp[i] or dp[i][j]LIS, LCS
Intervaldp[i][j]MCM, Palindrome
Bitmaskdp[mask]TSP, Subset problems

💡 Tip: DP ต้องฝึกเยอะๆ ยิ่งทำโจทย์มากยิ่งเห็น pattern ง่ายขึ้น