[LeetCode]Knight Probability in Chessboard

递归的方法很容易想，思路如下:

• 如果当前超出board，return 0
• 如果当前剩余0步并且在board里，return 1
• 否则八个方向分别递归，结果乘以0.125累加

纯dfs很慢，我们用memorization优化即可。时间复杂度O(N^2 * K)，空间复杂度O(N^2 * K)。代码如下：

	class Solution {
	public:
	double knightProbability(int N, int K, int r, int c) {
	if (r < 0 || r >= N || c < 0 || c >= N)return 0;
	if (!K)return 1;
	if (memo.find(r * N + c) != memo.end() && memo[r * N + c].find(K) != memo[r * N + c].end())return memo[r * N + c][K];
	vector<pair<int, int>> dirs = { { 1, 2 },{ 2, 1 },{ 2, -1 },{ 1, -2 },{ -1, -2 },{ -2, -1 },{ -2, 1 },{ -1, 2 } };
	double prob = 0;
	for (auto& dir : dirs)
	{
	int x = r + dir.first, y = c + dir.second;
	prob += 1.0 / 8 * knightProbability(N, K - 1, x, y);
	}
	memo[r * N + c][K] = prob;
	return prob;
	}
	private:
	unordered_map<int, unordered_map<int, double>> memo;
	};

view raw Knight Probability in Chessboard_1.cpp hosted with ❤ by GitHub

bottom up的方法一样也可以做。DP[i][j][k]代表位于[i, j]位置并且还剩k步的时候位于board内的概率，我们有递推方程:

• DP[i][j][k] = sum(0.125 * DP[x][y][k - 1]), where we can move from i, j to x, y

时间复杂度O(N^2 * K)，空间复杂度可以用滚动数组优化到O(N^2)。代码如下:

	class Solution {
	public:
	double knightProbability(int N, int K, int r, int c) {
	if (r < 0 || r >= N || c < 0 || c >= N)return 0;
	if (!K)return 1;
	vector<pair<int, int>> dirs = { { 1, 2 },{ 2, 1 },{ 2, -1 },{ 1, -2 },{ -1, -2 },{ -2, -1 },{ -2, 1 },{ -1, 2 } };
	//dp[i][j][k] represents the probablity we still stay in board when we are at i, j and have k steps left
	//dp[i][j][k] = sum(0.125 * dp[x][y][k - 1]), where we can move from x, y to i, j
	//we can use rolling array to reduce the space complexity to O(N^2)
	//base case: dp[i][j][0] = 1, for every i and j
	vector<vector<vector<double>>> dp(N, vector<vector<double>>(N, vector<double>(2, 0)));
	for (int i = 0; i < N; ++i)
	{
	for (int j = 0; j < N; ++j)
	{
	dp[i][j][0] = 1.0;
	}
	}
	int e = 1;
	for (int k = 1; k <= K; ++k, e ^= 1)
	{
	for (int i = 0; i < N; ++i)
	{
	for (int j = 0; j < N; ++j)
	{
	dp[i][j][e] = 0;
	for (auto& dir : dirs)
	{
	int x = i + dir.first, y = j + dir.second;
	if (x >= 0 && x < N && y >= 0 && y < N)
	dp[i][j][e] += 0.125 * dp[x][y][e ^ 1];
	}
	}
	}
	}
	return dp[r][c][e ^ 1];
	}
	};

view raw Knight Probability in Chessboard_2.cpp hosted with ❤ by GitHub