Xác suất đến đúng điểm với bước 2 hoặc 3 trong C++

Người A đi từ X=0, mỗi bước hoặc đi 2 (xác suất p) hoặc 3 (xác suất 1-p). Tìm xác suất đến đúng X = num.

Ví dụ 1

Input – num = 5, p = 0.2

Output – 0.32

Giải thích: 2 cách đến 5: 2+3 (p×(1-p)=0.16) và 3+2 ((1-p)×p=0.16). Tổng = 0.32.

Ví dụ 2

Input – num = 2, p = 0.1

Output – 0.1

Thuật toán Quy hoạch động

dp[i] = xác suất đến đúng i.

• dp[0] = 1 (đã ở đích)
• dp[1] = 0 (không thể đến 1 bằng bước 2,3)
• dp[2] = p
• dp[3] = 1-p
• dp[i] = p × dp[i-2] + (1-p) × dp[i-3] với i ≥ 4

Ví dụ code

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

double probabilityReach(int target, double p) {
    if (target < 0) return 0;
    vector<double> dp(target + 1, 0);
    dp[0] = 1;
    if (target >= 1) dp[1] = 0;
    if (target >= 2) dp[2] = p;
    if (target >= 3) dp[3] = 1 - p;
    
    for (int i = 4; i <= target; i++) {
        dp[i] = p * dp[i-2] + (1-p) * dp[i-3];
    }
    return dp[target];
}

int main() {
    int num = 5;
    double p = 0.2;
    cout << "Probability: " << probabilityReach(num, p) << endl;
    return 0;
}

Kết quả

Probability: 0.32

Lưu ý: Nếu target = 1 → 0. Target = 0 → 1. Code xử lý các trường hợp biên.