Bài Toán Bàn Phím Di Động (Mobile Numeric Keypad Problem)

Giới thiệu

Cho bàn phím số di động 4x3 (có * và # không được nhấn). Chỉ được di chuyển lên, xuống, trái, phải từ phím hiện tại. Tìm số lượng số có n chữ số có thể tạo được.

Đầu vào và Đầu ra

Đầu vào: Số chữ số n = 3
Đầu ra: 138 số có thể tạo được.

Thuật toán Quy hoạch động

Bảng count[10][n+1] lưu số cách tạo số độ dài k bắt đầu từ chữ số i. Duyệt từng ô trên bàn phím, cập nhật theo 4 hướng di chuyển.

getCount(n)
Begin
    if n <= 0 return 0; if n = 1 return 10
    định nghĩa mảng row[5] = {0,0,-1,0,1}, col[5] = {0,-1,0,1,0}
    count[10][n+1]; khởi tạo count[i][0]=0, count[i][1]=1
    for k := 2 to n do
        for i := 0 to 3 do
            for j := 0 to 2 do
                nếu keypad[i][j] không phải * hoặc # thì
                    num := keypad[i][j]
                    count[num][k] := 0
                    for mỗi hướng di chuyển do
                        rowMove := i + row[move]; colMove := j + col[move]
                        nếu hợp lệ và không phải *,# thì
                            nextNum := keypad[rowMove][colMove]
                            count[num][k] += count[nextNum][k-1]
                        done
                    done
            done
        done
    done
    totalCount := sum count[i][n] cho i=1..9
    return totalCount
End

Ví dụ 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 (n <= 0) return 0;
    if (n == 1) return 10;
    int row[] = {0, 0, -1, 0, 1};
    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 << "Số chữ số: "; cin >> n;
    cout << "Số tổ hợp có thể: " << getCount(n);
    return 0;
}

Kết quả

Số chữ số: 3
Số tổ hợp có thể: 138