AOJ - SNAIL

AOJ - SNAIL

$dp[i][j]=$ $i$ 번째 날이고 $j$ 만큼 올라왔을 때 $m$ 일까지 갔을 때 $n$ 이상일 확률

이라고 할 때,

$dp[i][j]=0.75 \cdot dp[i+1][j+2] + 0.25 \cdot dp[i+1][j+1]$ 이 된다.

void solve() {  
   int n, m;  
   cin >> n >> m;  
   vector<vector<double>> dp(m + 1, vector<double>(n * 2 + 1, -1));  
   function<double(int, int)> fn = [&](int i, int j) -> double {  
      if (j >= n) return 1;  
      if (i == m) return 0;  
      double &ret = dp[i][j];  
      if (ret > -0.5) return ret;  
  
      return ret = 0.75 * fn(i + 1, j + 2) + 0.25 * fn(i + 1, j + 1);  
   };  
   cout.precision(15);  
   cout << fixed << fn(0, 0) << endl;  
}