Mobile Numeric Keypad Problem (จำนวนตัวเลขที่พิมพ์ได้บนคีย์패ด)

กำหนด Numeric Keypad แบบมือถือเก่า:

1 2 3
4 5 6
7 8 9
* 0 #

กฎ: จากปุ่มปัจจุบัน กดได้เฉพาะ บน, ล่าง, ซ้าย, ขวา (ไม่ได้กดแนวทแยง) และ ห้ามกด * และ #

หาจำนวนตัวเลข n หลักที่พิมพ์ได้ตามกฎนี้

ตัวอย่าง Input และ Output

Input: n = 3 (3-digit numbers)
Output: Possible Combinations: 138

อัลกอริทึม Dynamic Programming

ฟังก์ชัน getCount(n)

กำหนด:

count[num][len] = จำนวนตัวเลขความยาว len ที่เริ่มต้นด้วย num

Recurrence:

count[num][k] = Σ count[nextNum][k-1] สำหรับ nextNum ที่อยู่ติดกับ num (4 ทิศทาง)

ขั้นตอน:

1. Base case: count[i][0] = 0, count[i][1] = 1 สำหรับทุก i (0-9)
2. for k = 2 ถึง n:
   • สำหรับทุกปุ่มบน keypad (ยกเว้น *, #):
     • ลองเดิน 4 ทิศทาง (บน, ล่าง, ซ้าย, ขวา)
     • ถ้าอยู่ในขอบเขตและไม่ใช่ *, # → รวม count[nextNum][k-1]
3. ผลรวม count[i][n] สำหรับ i = 0..9

ตัวอย่างโค้ด C++

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

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

int getCount(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 10; // 0-9

    int row[] = {0, 0, -1, 0, 1}; // stay, left, up, right, down
    int col[] = {0, -1, 0, 1, 0};

    int count[10][n+1];
    for (int i = 0; i <= 9; i++) {
        count[i][0] = 0;
        count[i][1] = 1;
    }

    for (int k = 2; k <= n; k++) {
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 3; j++) {
                if (keypad[i][j] != '*' && keypad[i][j] != '#') {
                    int num = keypad[i][j] - '0';
                    count[num][k] = 0;
                    for (int move = 0; move < 5; move++) {
                        int rowMove = i + row[move];
                        int colMove = j + col[move];
                        if (rowMove >= 0 && rowMove <= 3 && colMove >= 0 && colMove <= 2 &&
                            keypad[rowMove][colMove] != '*' && keypad[rowMove][colMove] != '#') {
                            int nextNum = keypad[rowMove][colMove] - '0';
                            count[num][k] += count[nextNum][k-1];
                        }
                    }
                }
            }
        }
    }

    int 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);
    return 0;
}

Output

Number of digits: 3
Possible Combinations: 138

ความซับซ้อน

• Time: O(n) - คงที่ต่อแต่ละ k (keypad มีขนาดคงที่ 10 ปุ่ม)
• Space: O(n) - ตาราง count[10][n+1]

ตารางค่าตัวอย่าง