สมมติว่า Rima เล่นเกมต่อไปนี้ซึ่งอิงจากเกมไพ่ "21" อย่างหลวม ๆ ดังนั้น Rima เริ่มต้นด้วย 0 แต้ม และจั่วตัวเลขในขณะที่เธอมีแต้มน้อยกว่า K ตอนนี้ ในระหว่างการจับฉลากแต่ละครั้ง เธอจะได้รับคะแนนจำนวนเต็มจากการสุ่มจากช่วง [1, W] โดยที่ W จะได้รับ และนั่นคือจำนวนเต็ม ตอนนี้แต่ละงวดเป็นอิสระและผลลัพธ์มีความน่าจะเป็นเท่ากัน Rima หยุดดึงตัวเลขเมื่อเธอได้รับ K หรือมากกว่านั้น เราต้องหาความน่าจะเป็นที่เธอได้ N หรือน้อยกว่านั้นไหม
ดังนั้นถ้า N =6, K คือ 1 และ W คือ 10 คำตอบจะเป็น 0.6 เมื่อ Rima ได้ไพ่ใบเดียวแล้วก็หยุด ใน 6 ใน 10 ความน่าจะเป็น เธออยู่ที่หรือต่ำกว่า N =6 คะแนน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ถ้า k เป็น 0 หรือ N>=K + W ให้คืนค่า 1
- สร้างอาร์เรย์ dp ขนาด N + 1 ตั้งค่า dp[0] :=1
- set wsum :=1.0, ret :=0.0
- สำหรับฉันอยู่ในช่วง 1 ถึง N
- dp[i] :=wsum / W
- ถ้าฉัน
- ถ้า i – W>=0 แล้ว wsum :=wsum – dp[i - W]
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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));
} อินพุต
6 1 10
ผลลัพธ์
0.6
