家装博览会2023_密云seo排名优化培训_最新seo网站优化教程_软文写手

问题背景

象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 L 的形状)。
象棋骑士可能的移动方式如下图所示：

我们有一个象棋骑士和一个电话垫，如下所示，骑士只能 站在一个数字单元格上（即蓝色单元格）。

给定一个整数 $n$，返回我们可以拨多少个长度为 $n$ 的不同电话号码。
你可以将骑士放置在 任何数字单元格上，然后你应该执行 $n-1$ 次移动来获得长度为 $n$ 的号码。所有的跳跃应该是 有效 的骑士跳跃。
因为答案可能很大，所以输出答案模 $10^9+7$。

数据约束

• $1\le n\le 5000$

解题过程

自己做的时候仍然模拟了棋盘上的八个方向，想判断边界，导致栈溢出了。
实际上这题每个位置上能够到达的下一个位置是固定的，这也是递推实现中状态转移方程的来源。

不过感觉自己动态规划差一些基础的理论知识，这题转递推没能掌握，先放一放。

具体实现

class Solution {private static final int MOD = 1000000007;// 定义一个数组来映射每个位置上能够到达的下一个位置private static final int[][] NEXT = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9}, {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}};public int knightDialer(int n) {int[][] memo = new int[5000][10];int res = 0;// j 枚举能够到达的下一个位置for(int j = 0; j < 10; j++) {// 实际上从小到大还是从大到小递归没有逻辑上的差别，但是从大到小递归可以少传一个参数res = (res + dfs(n - 1, j, memo)) % MOD;}return res;}private int dfs(int i, int j, int[][] memo) {if(i == 0) {return 1;}if(memo[i][j] != 0) {return memo[i][j];}int res = 0;for(int next : NEXT[j]) {res = (res + dfs(i - 1, next, memo)) % MOD;}return memo[i][j] = res;}
}