Guess Number Higher or Lower II ใน C++: หาต้นทุนต่ำสุดเพื่อเดาตัวเลข

โจทย์

เกมเดาตัวเลข 1..n เดาผิดจ่ายเงินเท่าตัวเลขที่เดา รู้ว่าเป้าหมายสูง/ต่ำ หาต้นทุนต่ำสุดที่รับประกันชนะ (worst case)

ตัวอย่าง: n=10, เป้าหมาย=8 เดา 5→จ่าย5, เดา7→จ่าย7, เดา9→จ่าย9 รวม 21 แต่ optimal strategy ให้ต้นทุนต่ำกว่า

แนวคิด: DP Minimax (Interval DP)

cost(lo, hi) = ต้นทุนต่ำสุดสำหรับช่วง [lo, hi]
ลองเดา i ทุกตัว: cost = i + max(cost(lo, i-1), cost(i+1, hi)) (worst case)
เลือก i ให้ cost น้อยที่สุด

ขั้นตอน

1. สร้าง dp[n+1][n+1] ใส่ -1
2. cost(lo, hi):
   • ถ้า lo >= hi → return 0
   • ถ้า dp[lo][hi] != -1 → return
   • ans = INF
   • ลูป i = lo ถึง hi: ans = min(ans, i + max(cost(lo,i-1), cost(i+1,hi)))
   • dp[lo][hi] = ans
3. คืน cost(1, n)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int cost(int lo, int hi, vector<vector<int>>& dp) {
        if (lo >= hi) return 0;
        if (dp[lo][hi] != -1) return dp[lo][hi];
        
        int ans = INT_MAX;
        for (int i = lo; i <= hi; i++) {
            ans = min(ans, i + max(cost(lo, i-1, dp), cost(i+1, hi, dp)));
        }
        return dp[lo][hi] = ans;
    }
    
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n+1, vector<int>(n+1, -1));
        return cost(1, n, dp);
    }
};

int main() {
    Solution ob;
    cout << ob.getMoneyAmount(8); // 12
    return 0;
}

อินพุต / เอาต์พุต

Input: 8

Output: 12

ความซับซ้อน

• Time: O(n³) - state n² แต่ละลูป n
• Space: O(n²)

ข้อสังเกต

สามารถปรับปรุงเป็น O(n²) ได้ด้วย Knuth Optimization หรือการสังเกตว่า optimal i อยู่ใกล้กลาง