เกม 21 ใหม่ (New 21 Game) ใน C++

ริมาเริ่มต้น 0 คะแนน จั่วไพ่ได้คะแนนสุ่ม 1 ถึง W จนกว่าจะได้ ≥ K คะแนน หาความน่าจะเป็นที่คะแนนสุดท้าย ≤ N

ตัวอย่าง

Input − N=6, K=1, W=10 Output − 0.6

คำอธิบาย − จั่ว 1 ครั้งหยุด (K=1) โอกาสได้ 1-6 คือ 6/10 = 0.6

แนวทางการแก้ปัญหา (Dynamic Programming + Sliding Window)

• dp[i] = ความน่าจะเป็นที่ได้คะแนน i
• dp[0] = 1
• สำหรับ i=1..N: dp[i] = (dp[i-1] + ... + dp[i-W]) / W (ใช้ sliding window sum)
• ถ้า i < K: ยังจั่วต่อ → เพิ่มเข้า window sum
• ถ้า i ≥ K: หยุดจั่ว → บวกเข้า answer
• ลบ dp[i-W] ออกจาก window เมื่อ i ≥ W

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

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

class Solution {
public:
    double new21Game(int N, int K, int W) {
        if (K == 0 || N >= K + W) return 1.0;
        vector dp(N + 1, 0);
        dp[0] = 1;
        double windowSum = 1, ans = 0;
        
        for (int i = 1; i <= N; i++) {
            dp[i] = windowSum / W;
            if (i < K) windowSum += dp[i];
            else ans += dp[i];
            if (i >= W) windowSum -= dp[i - W];
        }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << fixed << setprecision(1) << ob.new21Game(6, 1, 10); // 0.6
    return 0;
}

ผลลัพธ์

0.6