935.骑士拨号器 - 力扣-易微帮

935.骑士拨号器 - 力扣

题目：

在这里插入图片描述

示例 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 vector<vector<int>>fromNum = {{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 < 10; i++) dp[1][i] = 1;

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

代码：

暴力求解：

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

# include<iostream>
# include<set>
# include<string>
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<string> answer;
void search(int n, string temp_string, int temp_number, int pos_x, int pos_y){
//	cout<<temp_string<<endl; 
	// 如果达到了边界，就进行存入数据，并且返回。 
	if(temp_number == n){
		answer.insert(temp_string);
//		cout<<temp_string<<endl;
		return ;
	}
	// 如果没有达到边界，就继续进行递归累加
	// 一共有八种方向，每一个方向都进行尝试
	for(int dire = 0;dire < direction_number; dire ++){
		int temp_x = pos_x + x[dire];
		int temp_y = pos_y + y[dire];
		if(temp_x >= min_x && temp_x <= max_x && temp_y >= min_y && temp_y <= max_y){  // 判断是否越界 
			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; cin>>n;
	int n = 14;
	int rows = sizeof(a) / sizeof(a[0]);
	int colums = sizeof(a[0]) / sizeof(a[0][0]);
	// 初始位置可以是任意一个数字的位置
	for(int row = 0;row < rows; row++){
		for (int colum = 0; colum < colums; colum ++){
			if(row == 3 && colum == 0 || row == 3 && colum == 2) continue;
			string num_to_string = to_string(a[row][colum]);
			search(n, num_to_string, 1, row, colum);
		}
	}
	
	cout<<answer.size() % mod<<endl;
	

//	for(int row = 0;row < rows; row++){
//		for (int colum = 0; colum < colums; colum ++){
//			printf("%d ", a[row][colum]);
//		}
//
//	}
	return ;
}

signed main(){
	IOS int t = 1;
	while(t--){
		solve();
	}
	return 0;
}

动态规划：

调试代码：

#include<iostream>
#include<vector>
using namespace std;
# define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
# define ll long long

const ll mod = 1e9 + 7;
const vector<vector<int>>fromNum = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0}, {}, {1, 7, 0}, {2, 6}, {1, 3}, {4, 2}};
void solve(){
//	int n;cin>>n;
	int N = 3131;
	int ans = 0;
	vector<vector<ll>>dp(N + 1, vector<ll>(10, 0));
	// 初始化边界, 一次的电话号码个数 
	for(int i = 0; i < 10;i ++)dp[1][i] = 1;
	// 进行动态规划, 从两次开始 
	for(int n = 2; n<= N;n ++){
		for(int j = 0;j < 10; j++){
			for(int from : fromNum[j]){
				dp[n][j] = (dp[n][j] + dp[n - 1][from]) % mod;
			}
		} 
	}
//	for(int i = 0;i <= N; i++){
//		for(int j = 0;j < 10;j ++){
//			cout<<dp[i][j]<<' ';
//		}
//		cout<<endl;
//	}
	for(int i = 0;i < 10;i ++) ans = (ans + dp.back()[i]) % mod;
	cout<<ans<<endl;
	
	return ;
}


int main(){
	IOS int t = 1;
	while(t--){
		solve();
	}
	return 0;
}

提交代码：

class Solution {
public:
    const long long mod = 1e9 + 7;
    const vector<vector<int>>fromNum = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0}, {}, {1, 7, 0}, {2, 6}, {1, 3}, {4, 2}};
    int knightDialer(int N) {
        // int N = 3131;
        int ans = 0;
        vector<vector<long long>>dp(N + 1, vector<long long>(10, 0));
        // 初始化边界, 一次的电话号码个数 
        for(int i = 0; i < 10;i ++)dp[1][i] = 1;
        // 进行动态规划, 从两次开始 
        for(int n = 2; n<= N;n ++){
            for(int j = 0;j < 10; j++){
                for(int from : fromNum[j]){
                    dp[n][j] = (dp[n][j] + dp[n - 1][from]) % mod;
                }
            } 
        }
        for(int i = 0;i < 10;i ++) ans = (ans + dp.back()[i]) % mod;
        
        return ans;
    }
};

935.骑士拨号器 - 力扣