動的計画法でゲームの目標スコアに到達する方法の数を数える方法

問題の概要

プレイヤーが1回のムーブごとに3、5、または10のいずれかのスコアを獲得できるゲームを考えてみましょう。ここに目標スコアが与えられ、その目標に到達する方法が何通りあるかを求めるのが課題です。

この問題は動的計画法(DP)を使うことで効率的に解けます。0からnまでの各スコアに対応するテーブルを用意し、3、5、10のそれぞれの点数について順番にテーブルを更新していきます。

入力と出力

入力:
3、5、10を使って到達すべき最大スコア。ここでは入力を50とします。

出力:
(3, 5, 10)を使って50に到達する方法の数: 14

アルゴリズム

到達可能なスコアは3、5、10の3種類のみです。

入力: n は到達すべき最大スコア

出力: スコア n に到達する方法の総数

Begin
    create table of size n+1
    set all table entries to 0
    table[0] := 1

    for i := 3 to n, do
        table[i] := table[i] + table[i-3]
    done

    for i := 5 to n, do
        table[i] := table[i] + table[i-5]
    done

    for i := 10 to n, do
        table[i] := table[i] + table[i-10]
    done

    return table[n]
End

このアルゴリズムのポイントは、table[0] を 1 で初期化することです。これは「スコア0に到達する方法は1通り(何もしない)」という意味になります。その後、3、5、10の順に、各点数を使って到達できる方法の数を累積的に更新していきます。

なお、点数ごとにループを回すこの処理順序では、組み合わせ(順序を区別しない数え方)でカウントされます。例えば「3→5」と「5→3」は同じ1通りとして扱われます。

C++での実装例

#include <iostream>
using namespace std;

// スコア n に到達する方法の数を返す
int countWay(int n) {
    int table[n+1], i;    // 各値 i に対する到達方法数を格納するテーブル

    for(int i = 0; i<=n; i++) {
        table[i] = 0;     // テーブルの全要素を0で初期化
    }

    table[0] = 1;         // スコア0の場合は1通りと設定
    for (i=3; i<=n; i++)  // 3を使う場合で更新
        table[i] += table[i-3];

    for (i=5; i<=n; i++)  // 5を使う場合で更新
        table[i] += table[i-5];

    for (i=10; i<=n; i++) // 10を使う場合で更新
        table[i] += table[i-10];

    return table[n];
}

int main() {
    int n;
    cout << "Enter max score: ";
    cin >> n;
    cout << "Number of ways to reach using (3, 5, 10)" << n << ": " << countWay(n);
}

実行結果

Enter max score: 50
Number of ways to reach using (3, 5, 10)50: 14

計算量

時間計算量: 3種類の点数それぞれについて n 回のループを行うため、O(3n)=O(n) です。

空間計算量: サイズ n+1 のテーブルを使用するため、O(n) です。