SNAIL (하, p. 258)

점화식: f(n,m) = f(n-1,m-1)*0.25 + f(n-1,m-2)*0.75

점화식 설명

n을 m개의 1,2로 만드는 방법은 f(n,m)

n-1을 m-1개의 1,2로 만드는 방법에서 마지막에 1을 쓰는 방법과 f(n-1,m-1)

n-1을 m-1개의 1,2로 만드는 방법에서 마지막에 2를 쓰는 방법으로 나눌 수 있고, f(n-1,m-2)

마지막에 1을 쓰는 방법은 확률 0.25를 곱하고,

마지막에 2를 쓰는 방법을 확률 0.75를 곱하면 된다.

#include <bits/stdc++.h>
using namespace std;
double dp[1001][1001];
bool chk[1001][1001];
double f(int n, int m) {
    if(m>=n) return 1;
    if(n==0 || m==0) return 0;
    if(chk[n][m]) return dp[n][m];

    chk[n][m] = true;
    double & ret = dp[n][m];
    return ret = f(n-1,m-1)*0.25 + f(n-2,m-1)*0.75;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        int n, m; cin >> n >> m;
        printf("%.8lf\n", f(n,m));
    }
    return 0;
}