935.骑士拨号器 - 力扣

935.骑士拨号器 - 力扣

题目链接：935. 骑士拨号器 - 力扣（LeetCode）

题目：

示例 1：

输入：n = 1
输出：10
解释：我们需要拨一个长度为1的数字，所以把骑士放在10个单元格中的任何一个数字单元格上都能满足条件。

示例 2：

输入：n = 2
输出：20
解释：我们可以拨打的所有有效号码为[04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]

示例 3：

输入：n = 3131
输出：136006598
解释：注意取模

题解：

题目大意：给定一个电话垫，不同数字之间的移动只能是L形状的路线（L可以旋转），并且只能在数字之间移动，求出长度为n的不同电话号码有多少个？

读完题目之后，一个很简单的思路就是模拟，使用暴力的方式来模拟这一过程，最初我是用的是深度优先搜索算法进行暴力求解，但是回出现栈溢出的情况，在输入N = 3131的时候，电脑内存爆满，导致电脑卡死，而后重启得以恢复。因此需要想出一个更加高效的方法，另一个思路就是——动态规划算法，我们可以定义dp[i][j]，表示长度为i终点为数字j的电话号码个数，由于每一个数字能移动到其他数字的个数是有限的，我们可以将其列举出来：

终点数字	起点数字
0	4， 6
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	4， 2

可以发现只有数字5移动到其他数字上，并且其他数字也不能移动到数字5上，因此我们可以设置一个vector数组，将其都存储进去，然后在循环的时候进行遍历这个数组，表示每个值能从那个位置移动而来，如果每一个数字能移动其他数字上，那么反过来也是成立的。

const vectorfromNum = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0}, {}, {1, 7, 0}, {2, 6}, {1, 3}, {4, 2}};

初始化数组，如果电话号码的长度为1，那么每一个数字都只不能移动，所以长度为1的每一个数字的值都为1。即：for(int i = 0; i

进行动态规划结束后，我们得到的是以每一个数字结尾的长度为n的电话号码个数，只需要将长度为N的每一个数字结尾的电话号码个数进行累加即可得到最终的答案（注意：还要进行取余）。

代码：

暴力求解：

该代码不能使用，会栈溢出，如果使用的话n的值不要超过17，如果超过17，就是不会使内存爆满，也会有漫长的等待时间。

# include
# include
# include
using namespace std;
# define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
# define ll long long
const ll mod = 10e9 + 7;
// 定义工具 
int x[8] = {2, 2, -2, -2, 1, -1, 1, -1};  // 左右 
int y[8] = {-1, 1, -1, 1, -2, -2, 2, 2};  // 上下 
int direction_number = sizeof(x) / sizeof(x[0]);
// 边界
int min_x = 0, min_y = 0;
int max_x = 2, max_y = 3; 
int a[][3] = {
	{1, 2, 3},
	{4, 5, 6},
	{7, 8, 9},
	{-1, 0, -1}
};
set answer;
void search(int n, string temp_string, int temp_number, int pos_x, int pos_y){
//	cout
		answer.insert(temp_string);
//		cout
		int temp_x = pos_x + x[dire];
		int temp_y = pos_y + y[dire];
		if(temp_x = min_x && temp_x   // 判断是否越界 
			if(a[temp_x][temp_y] == -1) continue;  		// 只能遍历到数字
			string num_to_string = to_string(a[temp_x][temp_y]);
			search(n, temp_string + num_to_string, temp_number + 1, temp_x, temp_y);
		}
	}
	
	return ;
}
void solve(){
//	int n; cinn;
	int n = 14;
	int rows = sizeof(a) / sizeof(a[0]);
	int colums = sizeof(a[0]) / sizeof(a[0][0]);
	// 初始位置可以是任意一个数字的位置
	for(int row = 0;row