935. Knight Dialer

• 전화 다이얼 위에서 체스의 나이트 말을 움직여서 만들 수 있는 번호의 경우의 수를 구하는 문제.

• 다이얼 위에서 말을 움직여 보면 아래와 같이 다음 숫자들이 정해지는 것을 알 수 있다.

1 → 6, 8 / 2 → 7, 9 / 3 → 4, 8 / 4 → 3, 9, 0 / 5 → 없음 /
6 → 1, 7, 0 / 7 → 2, 6 / 8 → 1, 3 / 9 → 2, 4 / 0 → 4, 6

• 첫번째 숫자부터 시작하여 다음 숫자로 가능한 경우의 수를 탐색해나간다.
• 이 때 계산해 둔 경우의 수를 matrix dp 에 기록해둔다.
• 번호의 최대 길이가 5000, 각 길이 마다 자리수는 10개이므로 총 50000 개를 기록할 수 있는 공간이 필요하다.
• 어차피 각 테스트 케이스 마다 저장되는 값이 동일하기 때문에 static 변수로 두는게 유리하다.

class Solution {
public:
    static constexpr int MOD = 1e9 + 7;
    static map<int, vector<int>> nextDigits;
    static vector<vector<int>> dp;

    int dfs(int n, int digit) {
        if (n == 1) return nextDigits[digit].size();
        if (dp[n][digit] != -1) return dp[n][digit];
        int result = 0;
        for (auto nextDigit : nextDigits[digit]) {
            result = (result + dfs(n - 1, nextDigit)) % MOD;
        }
        return dp[n][digit] = result;
    }

    int knightDialer(int n) {
        if (n == 1) return 10;
        int result = 0;
        for (int i = 0; i <= 9; ++i) {
            result = (result + dfs(n - 1, i)) % MOD;
        }
        return result;
    }
};

map<int, vector<int>> Solution::nextDigits = {
    {1, {6, 8}},
    {2, {7, 9}},
    {3, {4, 8}},
    {4, {3, 9, 0}},
    {5, {}},
    {6, {1, 7, 0}},
    {7, {2, 6}},
    {8, {1, 3}},
    {9, {2, 4}},
    {0, {4, 6}},
};

vector<vector<int>> Solution::dp(5000, vector<int>(10, -1));