LeetCode.935 骑士拨号器

题目链接

思路

动态规划

骑士每一步跳都会在号码后面增加一个新的数字，就会产生一个新的号码。
由于跳的方式是固定的，所以从某个数字可以跳到的其他数字也是固定的。

0 -> 4, 6;
1 -> 6, 8;
2 -> 7, 9;
3 -> 4, 8;
4 -> 3, 9, 0;
5 -> null;
6 -> 1, 7, 0;
7 -> 2, 6;
8 -> 1, 3;
9 -> 2, 4;

在这个基础上容易知道，要产生一个n位的号码，只需看第n-1位的数字是多少，然后根据这一位数字能够走到的位置k，得到可以得到k个新的号码。

所以，可以得到状态转移方程
$f(n, k) = \sum_{j->k} f(n - 1, j)$
其中f(n, k)代表长度为n尾号为k的号码的个数，在长度为n−1和n之间，如果骑士能够从j跳到k，则能够为生成尾号为k的号码提供1点贡献；如果有m个尾号为j的骑士，则能为生成尾号为k的号码提供m点贡献；若有不同的号码都能到k，则它们都能提供对应的贡献。

举个例子，因为6能到达1, 7, 0三个点，所以通过16这个号码，可以产生161, 167, 160三个号码；同理，因为从0, 1, 7三个点可以到达6，所以XXX6可以由XX0, XX1, XX7三个号码产生。通过统计XX0, XX1, XX7的个数进行求和，则可以得到这么多个XXX6。如果对长度为nn所有尾号进行计数，则可以得到长度为nn的号码的个数。

代码

public class Solution {
    const int MOD = (int)1e9 + 7;
    int[,] cnt;
    public int KnightDialer(int n) {
        cnt = new int[2, 10];
        int[][] list = new int[10][] {
            new int[2]{4, 6},
            new int[2]{6, 8},
            new int[2]{7, 9},
            new int[2]{4, 8},
            new int[3]{3, 9, 0},
            new int[0]{},
            new int[3]{1, 7, 0},
            new int[2]{2, 6},
            new int[2]{1, 3},
            new int[2]{2, 4},
        };
        for (int i = 0; i < 10; i++) {
            cnt[0, i] = 1;
        }
        int pre = 0, now = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 10; j++) {
                cnt[now, j] = 0;
            }
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < list[j].Length; k++) {
                    cnt[now, list[j][k]] = ((cnt[now, list[j][k]] % MOD) + (cnt[pre, j] % MOD)) % MOD;
                }
            }
            (now, pre) = (pre, now);
        }
        long res = 0;
        for (int j = 0; j < 10; j++) {
            res = ((res % MOD) + (cnt[pre, j] % MOD)) % MOD;
        }
        return (int)(res % MOD);
    }
}