HPが $H$ の化け猫を倒すことを考えます。
与ダメージ $A$ の通常攻撃は必ずヒットしますが、与ダメージ $D$ の必殺攻撃は $2/3$ の確率でしか成功せず、失敗したときはダメージを与えられません。
毎回どちらかの攻撃をしたとして、化け猫を倒すまでに攻撃する回数の期待値を最小とするように攻撃していったとき、
倒したときの攻撃回数の期待値はいくらですか。yukicoder No.23
$H, A, D$ はともに $10{,}000$ 以下。

#include <iostream>
#include <algorithm>
using namespace std;

const int inf = 987654321;
int h, a, d;

// 今までの与ダメージがdamageのときの
// 攻撃回数の最小の期待値を返す
double rec(int damage) {
  if(damage >= h) { return 0; }
  return min(rec(damage + a) + 1,
             rec(damage + d) + 3./2);
}

int main(void) {
  scanf("%d%d%d", &h, &a, &d);
  double res = rec(0);
  printf("%lf\n", res);
  return 0;
}
    

#include <iostream>
#include <algorithm>
using namespace std;

const int inf = 987654321;
vector<double> dp;
int h, a, d;

// 今までの与ダメージがdamageのときの
// 攻撃回数の最小の期待値を返す
double rec(int damage) {
  if(dp[damage] != inf) { return dp[damage]; }
  if(damage >= h) { return dp[damage] = 0; }
  return 
    dp[damage] = min(rec(damage + a) + 1,
                     rec(damage + d) + 3./2);
}

int main(void) {
  scanf("%d%d%d", &h, &a, &d);
  dp.assign(h+10, inf);
  double res = rec(0);
  printf("%lf\n", res);
  return 0;
}