PE645

题目大意是:

有D天，第1天与第D天相连。

每次随机选取1天作为假期。

然后如果某一天的前一天和后一天都是假期的话，那么这一天也变成假期。

求变成全部为假期的期望次数。

$O(n^2)$ DP怎么写啊