モバイルテンキーの問題 ― 上下左右の移動制限下で作れるn桁の数字列の総数を動的計画法で求める

問題概要

数字キーパッドを持つモバイル端末が与えられます。現在押しているキーから移動できるのは上下左右のキーのみで、斜め方向のキーへの移動は許可されません。また、「*」と「#」のキーは押すことができません。

桁数 n が与えられたとき、これらのルールを守りながらキーパッド上で作成できる n 桁の数字列の総数を求めます。なお、同じキーを連続して押すこと（現在位置にとどまること）は許されるものとします。

入力と出力

入力:
桁数（例：3桁の数字）
出力:
与えられた条件を満たして作成できる3桁の数字列の総数。この場合の答えは 138 です。

アルゴリズム

この問題は動的計画法（DP）を用いることで効率的に解くことができます。count[i][j] を「数字 i から始まる j 桁の数字列の個数」と定義します。長さ k の数字列の先頭キーが num であるとき、その次に押せるキーは num 自身とその上下左右の隣接キーだけなので、次の漸化式が成り立ちます。

count[num][k] = Σ count[nextNum][k−1]　（nextNum は num およびその上下左右にある有効なキー）

getCount(n)

入力: 桁数 n
出力: モバイルキーパッドで n 桁の数字列を入力できる組み合わせの総数

Begin
    if n <= 0, then
        return 0
    if n = 1, then
        return 10

    現在位置・上下左右への移動用に row 配列と col 配列を定義する
    サイズ (10 × n+1) の count テーブルを定義する

    for i in range 0 to 9, do
        count[i, 0] := 0
        count[i, 1] := 1
    done

    for k in range 2 to n, do
        for i in range 0 to 3, do
            for j in range 0 to 2, do
                if key[i, j] が * および # 以外ならば, then
                    num := key[i, j]
                    count[num, k] := 0
                    すべての可能な移動に対して, do
                        rowMove := i + row[move]
                        colMove := j + col[move]
                        if rowMove が (0..3) の範囲内 かつ colMove が (0..2) の範囲内
                           かつ 移動先のキーが * および # 以外ならば, then
                            nextNum := key[rowMove, colMove]
                            count[num, k] := count[num, k] + count[nextNum, k-1]
                    done
            done
        done
    done

    totalCount := 0
    for i in range 0 to 9, do
        totalCount := totalCount + count[i, n]
    done

    return totalCount
End

C++による実装例

#include <iostream>
using namespace std;

char keypad[4][3] = {
    {'1','2','3'},
    {'4','5','6'},
    {'7','8','9'},
    {'*','0','#'}
};

int getCount(int n) {
    if(keypad == NULL || n <= 0)
        return 0;

    if(n == 1)
        return 10;          // 1桁の数字は 0〜9 の10通り

    int row[] = {0, 0, -1, 0, 1};   // 上下移動では行が変化する

    int col[] = {0, -1, 0, 1, 0};   // 左右移動では列が変化する

    int count[10][n+1];             // 「数字 i から始まる長さ j の数字列」の数を格納
    int move=0, rowMove=0, colMove=0, num = 0;
    int nextNum=0, totalCount = 0;

    for (int i=0; i<=9; i++) {      // 長さ 0 と 1 の場合を初期化
        count[i][0] = 0;
        count[i][1] = 1;
    }

    for (int k=2; k<=n; k++) {              // 2桁目から n 桁目まで計算
        for (int i=0; i<4; i++ ) {          // 行方向に走査
            for (int j=0; j<3; j++) {       // 列方向に走査
                if (keypad[i][j] != '*' && keypad[i][j] != '#') {   // キーが * と # 以外の場合
                    num = keypad[i][j] - '0';           // 文字から数値を求める
                    count[num][k] = 0;

                    for (move=0; move<5; move++) {
                        rowMove = i + row[move];        // 行方向の移動配列を使って移動
                        colMove = j + col[move];        // 列方向の移動配列を使って移動
                        if (rowMove >= 0 && rowMove <= 3 && colMove >=0 && colMove <= 2 &&
                            keypad[rowMove][colMove] != '*' && keypad[rowMove][colMove] != '#') {
                            nextNum = keypad[rowMove][colMove] - '0';   // 隣接する次の数字を取得
                            count[num][k] += count[nextNum][k-1];       // 漸化式により個数を累積
                        }
                    }
                }
            }
        }
    }

    totalCount = 0;
    for (int i=0; i<=9; i++)        // 各数字から始まる場合の数をすべて合計
        totalCount += count[i][n];
    return totalCount;
}

int main() {
    int n;
    cout << "Number of digits: "; cin >> n;
    cout << "Possible Combinations: " << getCount(n);
}

出力

Number of digits: 3
Possible Combinations: 138

補足：計算量と結果の目安

各桁についてキーパッド上の最大10個のキーそれぞれに対し高々5方向の移動を調べるだけなので、時間計算量は O(n)（正確には O(10 × 5 × n)）となり、n が大きくなっても線形時間で処理できます。空間計算量も O(10 × n) です。

結果の目安として、n=1 の場合は 0〜9 の 10 通り、n=2 では 36 通り、n=3 では 138 通りの数字列が作成できます。