home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Stone Game III: เกมกองหินใน C++

ปัญหา

อмалและบีمالเล่นเกมกองหินที่เรียงเป็นแถว แต่ละกองมีค่า (stoneValue) สลับกันหยิบ 1-3 กองจากด้านหน้า คะแนน = ผลรวมค่ากองที่หยิบ ใครคะแนนมากกว่าชนะ (ออมลเริ่มก่อน) ทั้งคู่เล่น Optimally หาผลลัพธ์: "Amal", "Bimal", หรือ "Tie"

ตัวอย่าง: [1,2,3,7] → Bimal ชนะ (ออมลหยิบ 1+2+3=6, บีمالหยิบ 7)

แนวคิด: DP จากท้ายมาหน้า (Suffix DP)

State

dp[i] = คะแนนสูงสุดที่ผู้เล่นคนปัจจุบันได้ มากกว่าคู่แข่ง เมื่อเริ่มจาก index i (คือ score_current - score_opponent จาก suffix i..n-1)

Suffix Sum

sum[i] = ผลรวม stoneValue[i..n-1]

Recurrence

ผู้เล่นคนปัจจุบันหยิบ k = 1,2,3 กอง (ได้คะแนน sum[i] - sum[i+k]) แล้วคู่แข่งเล่นต่อจาก i+k ได้เปรียบ dp[i+k]

dp[i] = max_{k=1..3} ( sum[i] - sum[i+k] - dp[i+k] )
      = max_{k=1..3} ( sum[i] - dp[i+k] )   // เพราะ sum[i] - sum[i+k] = stones taken

จริงๆ แล้ว sum[i] - dp[i+k] มาจาก: คะแนนตัวเอง = taken, คะแนนคู่แข่ง = sum[i+k] - dp[i+k] → Diff = taken - (sum[i+k] - dp[i+k]) = sum[i] - sum[i+k] - sum[i+k] + dp[i+k] → ผิด

ถูกต้อง: ให้ dp[i] = คะแนนสูงสุดที่คนปัจจุบันได้จาก suffix i (ไม่ใช่ diff)

dp[i] = max( sum[i] - dp[i+1], sum[i] - dp[i+2], sum[i] - dp[i+3] )
      = sum[i] - min(dp[i+1], dp[i+2], dp[i+3])

เพราะ: คะแนนตัวเอง = sum[i] - sum[i+k], คะแนนคู่แข่งต่อไป = dp[i+k], รวมคะแนนตัวเอง = (sum[i] - sum[i+k]) + (sum[i+k] - dp[i+k]) = sum[i] - dp[i+k]

โค้ด C++

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

class Solution {
public:
    string stoneGameIII(vector<int>& v) {
        int n = v.size();
        vector<int> dp(n + 10, -1e9);
        vector<int> sum(n + 10, 0);
        
        // Suffix sum
        sum[n - 1] = v[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            sum[i] = sum[i + 1] + v[i];
        }
        
        // DP จากท้ายมาหน้า
        for (int i = n - 1; i >= 0; i--) {
            for (int k = i + 1; k <= i + 3 && k <= n; k++) {
                dp[i] = max(dp[i], sum[i] - dp[k]);
            }
        }
        
        int total = sum[0];
        int amal_score = dp[0];
        int bimal_score = total - amal_score;
        
        if (amal_score > bimal_score) return "Amal";
        if (amal_score == bimal_score) return "Tie";
        return "Bimal";
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 2, 3, 7};
    cout << ob.stoneGameIII(v);  // Bimal
    return 0;
}

ความซับซ้อน

  • Time: O(n)
  • Space: O(n)

Input / Output

Input:  {1,2,3,7}
Output: Bimal

ข้อสังเกตเพิ่มเติม

สามารถลด Space เหลือ O(1) ได้โดยเก็บแค่ dp[i+1], dp[i+2], dp[i+3] เพราะแต่ละ state ใช้แค่ 3 ค่าก่อนหน้า