yukicoder No.65 回数の期待値の練習 解説

問題文

解説

今回の問題のユーザー解説はみんな動的計画法動的計画法言っていたので、私は再帰関数を使った解説にする。

f(x) = \left\{
\begin{array}{ll}
(E(x+1)+E(x+2)+E(x+3)+E(x+4)+E(x+5)+E(x+6))\times \frac{1}{6}+1(X<K)&(X<K)\\
0&(X\geqq K)
\end{array}
\right.

これをそのままいい感じに解けばよい。
$K=20$のとき、下記のコードによる$E$の呼び出し回数は$2830273$回と十分に少ないので、わざわざメモ化再帰する必要もない。

C++での再帰関数解答例

#include <bits/stdc++.h>
using namespace std;

double E(int x,int K){
  if(x>=K)return 0;
  return (E(x+1,K)+E(x+2,K)+E(x+3,K)+E(x+4,K)+E(x+5,K)+E(x+6,K))/6+1;
}

int main(){
  int K;cin>>K;
  cout<<fixed<<setprecision(20);
  cout<<E(0,K)<<endl;
}

また、せっかくなのでメモ化再帰についてもやってみる。
再帰関数$E$の前にメモ用配列を用いて、すでにその数値を呼び出していたならそれをそのままリターンする、

メモ化再帰解答例

#include <bits/stdc++.h>
using namespace std;

//メモ化再帰用配列
vector<double> memo(30,-1);
double E(int x,int K){
  if(x>=K)return 0;
  if(memo[x]!=-1)return memo[x];
  double c=(E(x+1,K)+E(x+2,K)+E(x+3,K)+E(x+4,K)+E(x+5,K)+E(x+6,K))/6+1;
  memo[x]=c;
  return c;
}

int main(){
  int K;cin>>K;
  cout<<fixed<<setprecision(20);
  cout<<E(0,K)<<endl;
}