【Python】AtCoderの問題から学ぶ動的計画法(DP)の基本

AtCoder

動的計画法(DP)について勉強したことをまとめておきます。ここでは、AtCoder Beginner Contest 153の問題Eを例にしたいと思います。

問題

トキはモンスターと戦っています。

モンスターの体力は H です。

トキは N 種類の魔法が使え、i 番目の魔法を使うと、モンスターの体力を Ai 減らすことができますが、トキの魔力を Bi 消耗します。

同じ魔法は何度でも使うことができます。魔法以外の方法でモンスターの体力を減らすことはできません。

モンスターの体力を 0 以下にすればトキの勝ちです。

トキがモンスターに勝つまでに消耗する魔力の合計の最小値を求めてください。

考え方

例として、モンスターの体力Hは9とします。また、トキは3種類の魔法が使え、

(魔法の強さ, 消耗する体力) = (8, 3), (4, 2), (2, 1)の場合を考えます。

出来るだけトキの体力の消耗を最小限にしつつ、モンスターの体力を減らしたいです。最もトキの消耗が少ないのは、まず、強さ8の魔法を使い、次に、強さ2の魔法を使う場合、または、その逆です。

これを動的計画法で解いていきます。

3つの魔法をそれぞれA, B, Cとしています。

「モンスターの体力を i 減らすための消耗の最小値(DP[i])」を順を追って探していきたいと思います。

まず、モンスターの体力を1減らしたい場合(DP[1])を考えます。この時、Cの魔法を使うと消耗が1となり最小です。

  • DP[1] = Cの消耗
  • DP[2] = Cの消耗

すでに求めた「モンスターの体力を1減らす場合の消耗の最小値」に足していきます。

  • DP[3] = DP[1] + Cの消耗
  • DP[4] = DP[2] + Cの消耗
  • DP[5] = DP[3] + Cの消耗 または DP[1] + Bの消耗
  • DP[6] = DP[4] + Cの消耗 または DP[2] + Bの消耗

BやCを使うよりも、Aを使った方が消耗が少なくなります。

  • DP[7] = Aの消耗
  • DP[8] = Aの消耗
  • DP[9] = DP[7] + Cの消耗 または DP[1] + Aの消耗

以上の流れから、

  1. DP[i] = DP[i-(Aの魔法の強さ)] + (Aによる消耗)
  2. DP[i] = DP[i-(Bの魔法の強さ)] + (Bによる消耗)
  3. DP[i] = DP[i-(Cの魔法の強さ)] + (Cによる消耗)

の最小値を求めれば良いことがわかります。

実装

モンスターの体力が0になった後も攻撃しない限り、「(モンスターの体力) + (魔法の強さの最大値)」を超えることはありません。そのため、iは(モンスターの体力) + (魔法の強さの最大値)を超えない範囲で考えます。

タイトルとURLをコピーしました