解法
動的計画法(メモ化再帰)するだけ。(独力で解けたのでメッチャ嬉しい)
コード
public class PerfectMemory {
private double[][] dp;
public double getExpectation(int N, int M) {
int C = N * M;
dp = new double[C + 1][C + 1];
double ans = dp(C, 0);
for (int i = 0; i <= C; i += 2) {
for (int j = 0; j <= 2; j++) {
System.out.print(dp[i][j] + "\t");
}
System.out.println();
}
return ans;
}
private double dp(int all, int open) {
if (all < open * 2) {
return 0.0;
}
if (dp[all][open] > 0.0) {
return dp[all][open];
}
dp[all][open] = 1.0;
if (all == 2) {
return dp[all][open];
}
if (open == 0) {
double hit = (double) 1.0 / (all - 1);
dp[all][open] += hit * dp(all - 2, open);
dp[all][open] += (1.0 - hit) * dp(all, open + 2);
return dp[all][open];
}
int close = all - open;
dp[all][open] += dp(all - 2, open - 1) * open / close;
dp[all][open] += (dp(all - 2, open) + 1.0) * (close - open) / close
* open / (close - 1);
dp[all][open] += dp(all - 2, open) * (close - open) / close * 1.0
/ (close - 1);
dp[all][open] += dp(all, open + 2) * (close - open) / close
* (close - open - 2) / (close - 1);
return dp[all][open];
}
}