Giả sử Rima chơi trò chơi sau, trò chơi đó dựa trên trò chơi bài "21" một cách lỏng lẻo. Vì vậy, Rima bắt đầu với 0 điểm, và vẽ các con số trong khi cô ấy có ít hơn K điểm. Bây giờ, trong mỗi lần rút thăm, cô ấy nhận được một số nguyên điểm ngẫu nhiên từ phạm vi [1, W], trong đó W được cho và đó là một số nguyên. Bây giờ mỗi trận hòa là độc lập và các kết quả có xác suất bằng nhau. Rima ngừng vẽ số khi cô ấy đạt K điểm trở lên. Chúng ta phải tìm xác suất để cô ấy có N điểm trở xuống?
Vì vậy, nếu N =6, K là 1 và W là 10, thì câu trả lời sẽ là 0,6, vì Rima nhận được một thẻ duy nhất, sau đó dừng lại, Trong 6 trên 10 xác suất, Cô ấy đạt hoặc thấp hơn N =6 điểm.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Nếu k bằng 0 hoặc N> =K + W, thì trả về 1
- tạo một mảng dp có kích thước N + 1, đặt dp [0]:=1
- đặt wsum:=1.0, ret:=0.0
- cho tôi trong phạm vi từ 1 đến N
- dp [i]:=wsum / W
- nếu i
- nếu i - W> =0, thì wsum:=wsum - dp [i - W]
- trả lời lại
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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;
double 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;
}
};
main(){
Solution ob;
cout << (ob.new21Game(6, 1, 10));
} Đầu vào
6 1 10
Đầu ra
0.6