TopCoder SRM 513 Div1 Medium: PerfectMemory

解法

動的計画法（メモ化再帰）するだけ。（独力で解けたのでメッチャ嬉しい）

コード

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];

	}

}