Xác suất đến các vị trí sau N bước trên đường số trong C++

Người đứng tại vị trí N trên đường số. Mỗi bước đi trái với xác suất L, phải với xác suất (1-L). Tính xác suất ở mỗi vị trí sau N bước.

Ví dụ

N=2, L=0.5 → Kết quả: [0.25, 0, 0.5, 0, 0.25] (vị trí 0,1,2,3,4)

Động quy hoạch (DP)

• dp[i][j]: xác suất ở vị trí j sau i bước.
• Khởi tạo: dp[1][N+1] = 1-L (phải), dp[1][N-1] = L (trái).
• Chuyển trạng thái:
  • Từ j-1 đi phải: dp[i][j] += dp[i-1][j-1] * (1-L)
  • Từ j+1 đi trái: dp[i][j] += dp[i-1][j+1] * L

Triển khai C++

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

void find_prob(int n, double low) {
    double high = 1 - low;
    vector<vector<double>> dp(n+1, vector<double>(2*n+1, 0));
    dp[1][n+1] = high;
    dp[1][n-1] = low;
    
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= 2*n; j++)
            dp[i][j] += dp[i-1][j-1] * high;
        for (int j = 2*n-1; j >= 0; j--)
            dp[i][j] += dp[i-1][j+1] * low;
    }
    
    for (int i = 0; i < 2*n+1; i++)
        cout << fixed << setprecision(2) << dp[n][i] << " ";
    cout << endl;
}

int main() {
    find_prob(2, 0.6);
    return 0;
}

Kết quả (n=2, L=0.6)

0.36 0.00 0.48 0.00 0.16

Vị trí: 0, 1, 2, 3, 4 (tương ứng chỉ số 0..4)

Độ phức tạp: O(N²) thời gian, O(N²) không gian (có thể tối ưu thành O(N)).