Trò chơi New 21 Game C++

Rima rút bài từ [1, W] cho đến khi đạt ≥ K điểm. Tính xác suất điểm cuối ≤ N.

Ví dụ

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

Giải thích - Rút 1 lá dừng. 6/10 khả năng ≤ 6.

Phương pháp tiếp cận (Dynamic Programming)

• dp[i] = xác suất đạt đúng i điểm
• Cửa sổ trượt wsum = tổng W dp trước đó
• dp[i] = wsum / W
• Nếu i < K: wsum += dp[i]; nếu i ≥ K: ans += dp[i]
• Loại bỏ dp[i-W] khỏi wsum khi i ≥ W

Ví dụ code 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<double> dp(N + 1);
        dp[0] = 1;
        double wsum = 1.0, ret = 0.0;
        for (int i = 1; i <= N; i++) {
            dp[i] = wsum / W;
            if (i < K) wsum += dp[i];
            else ret += dp[i];
            if (i - W >= 0) wsum -= dp[i - W];
        }
        return ret;
    }
};

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

Kết quả

0.6