骑士走键盘骑士走键盘

骑士走键盘标签（空格分隔）： algorithm
骑士在键盘上走日形状的个数

骑士在键盘上走日形状的个数，题目大意，在九宫格键盘的数字键上放置一个骑士，骑士走步，走的方式按照日字形，每走一步，认为是形成一个数组，最后构成位数，问能够形成多少个不同的数字。
例如：，那么可以形成这么十个数字。再如:那么可以形成如下数字
可以看到有如下的走法关系:

【骑士走键盘】 $骑士走键盘$
文章图片

注意4和6能够走到0。

方法一：递归

直观想法，第一步有10种选择，后面的每一步的选择都可以有上述表格获取。所以我们遍历这10种第一步。剩下的步骤可以从上述表中获取下一个步骤的具体走法。假设我们用，来表示从数字开始，走了步之后，再走步的方法。
表示当前i能够跳到的数字集合，例如：。

有个问题是，什么时候能够算作是完成一种走法呢？
完成一次走法必须满足的条件是走了n步，即时。
所以有如下的基本情况：
，认为方法数为1，

unordered_map> umap; const int M = int(1e9 + 7); int knightDialer(int N) { umap[0] = { 4, 6 }; umap[1] = { 6, 8 }; umap[2] = { 7, 9 }; umap[3] = { 4, 8 }; umap[4] = { 0, 3, 9 }; umap[5] = {}; umap[6] = { 0, 1, 7 }; umap[7] = { 2, 6 }; umap[8] = { 1, 3 }; umap[9] = { 2, 4 }; int c = 0; for (int i = 0; i < 10; i++) { c += knight(i, 1, N); c %= M; } return c; }int knight(int k, int step, int n) { if (step == n) return 1; auto list = umap[k]; int size = list.size(); int s = 0; for (int i = 0; i < size; i++) { int x = knight(list[i], step + 1, n); s += x % M; s %= M; } return s % M; }

时间复杂度:。
空间复杂度:。

方法二：转化为备忘录递归（自顶向下的方法）

上述方式存在子问题重复计算的情况，例如计算,需要计算 ,计算时，也需要计算，，可以发现非常多的子问题需要重新计算，我们用map，也可以用数组，来缓存已经计算完的数据。对于已经获取的数据直接返回结果。
对于已经计算出来的符号排列结果用map来保存，例如map[i-j]=x，表示选择结果。

unordered_map> umap; unordered_map cache; const int M = int(1e9 + 7); int knightDialer(int N) { umap.clear(); cache.clear(); umap[0] = { 4, 6 }; umap[1] = { 6, 8 }; umap[2] = { 7, 9 }; umap[3] = { 4, 8 }; umap[4] = { 0, 3, 9 }; umap[5] = {}; umap[6] = { 0, 1, 7 }; umap[7] = { 2, 6 }; umap[8] = { 1, 3 }; umap[9] = { 2, 4 }; int c = 0; for (int i = 0; i < 10; i++) { c += knight(i, 1, N); c %= M; } return c; }int knight(int k, int step, int n) { if (step == n) return 1; string key = to_string(k) + "-" + to_string(step); if (cache.find(key) != cache.end()) { return cache[key]; } auto list = umap[k]; int size = list.size(); int s = 0; for (int i = 0; i < size; i++) { int x = knight(list[i], step + 1, n); s += x % M; s %= M; } cache[key] = s % M; return cache[key]; }

时间复杂度：。
空间复杂度：，需要使用哈希表。
超时不通过，可优化。

方法三：转化为备忘录递归（自底向上的方法）（转化为迭代计算）

假设表示以开始，走步的形成数字方法。
那么,可以由，可以跳的数字的步数。

基础情况：

unordered_map> umap; const int M = int(1e9 + 7); int knightDialer(int N){ umap[0] = { 4, 6 }; umap[1] = { 6, 8 }; umap[2] = { 7, 9 }; umap[3] = { 4, 8 }; umap[4] = { 0, 3, 9 }; umap[5] = {}; umap[6] = { 0, 1, 7 }; umap[7] = { 2, 6 }; umap[8] = { 1, 3 }; umap[9] = { 2, 4 }; int c = 0; int size = 10; vector> dp(size, vector(N, 0)); // base case #1 for (int i = 0; i < size; i++) { dp[i][0] = 1; }for (int s = 1; s < N; s++) { for (int i = 0; i < size; i++) { auto next = umap[i]; for (auto e : next) { // dp[i][s] += dp[e][s - 1]; dp[i][s] %= M; } } } for (int i = 0; i < size; i++) { c += dp[i][N - 1]; c %= M; } return c % M; }