leetcode [688] “马”在棋盘上的概率

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

已知一个 NxN 的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0)，最右下角的记为 (N-1, N-1)。

现有一个 “马”（也译作 “骑士”）位于 (r, c) ，并打算进行 K 次移动。

如下图所示，国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。

现在 “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了 K 次或跳到了棋盘外面。

求移动结束后，“马” 仍留在棋盘上的概率。

示例：

输入: 3, 2, 0, 0
输出: 0.0625
解释: 
输入的数据依次为 N, K, r, c
第 1 步时，有且只有 2 种走法令 “马” 可以留在棋盘上（跳到（1,2）或（2,1））。对于以上的两种情况，各自在第2步均有且只有2种走法令 “马” 仍然留在棋盘上。
所以 “马” 在结束后仍在棋盘上的概率为 0.0625。

注意：

N 的取值范围为 [1, 25]
K 的取值范围为 [0, 100]
开始时，“马” 总是位于棋盘上

来自题解：

最简单的方法就是不断递归计算子问题，但是有很大的冗余技术

double getres(int N,int K,int step,int i,int j){
    if(i>N-1||j>N-1||i<0||j<0) return 0; //先判断坐标值是否越界，若越界直接返回0
    if(step==K) return 1; //若已经走了K步，并且是在棋盘上的，那么直接返回1
    double res=0;         //res用来记录在当前状态下，即已经走了step步数，并且到达i，j的情况下，棋子在棋盘上的概率
    res+=getres(N,K,step+1,i-1,j-2); //递归地走每一条子路径
    res+=getres(N,K,step+1,i-2,j-1);
    res+=getres(N,K,step+1,i-2,j+1);
    res+=getres(N,K,step+1,i-1,j+2);
    res+=getres(N,K,step+1,i+1,j+2);
    res+=getres(N,K,step+1,i+2,j+1);
    res+=getres(N,K,step+1,i+2,j-1);
    res+=getres(N,K,step+1,i+1,j-2);
    return res/8.0; //返回概率
}

因此使用动态规划，而且状态转移方程也比较简单：dp(step,i,j)=dp(step-1,i-1,j-2)+dp(step-1,i-2,j-1)+...+dp(step-1,i+2,j-1)+dp(step-1,i+1,j-2)

初步的动态规划：

double DP(int N, int K, int i, int j){
    vector<vector<vector<double>>> dp(K+1,vector<vector<double>>(N,vector<double>(N,0))); //根据上面的递归函数，我们知道，只需要3个参数，就可以获得答案
    dp[0][i][j]=1; //这个三维矩阵，其实就是dp[step][i][j]的形式。所以在一步都没走的情况下，在i，j的位置概率为1.
    for(int s=1;s<=K;s++){ //一个简单的动态规划,每一步的状态都依赖于前一步状态。
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++){
                double D1=(i>=1&&j>=2)?dp[s-1][i-1][j-2]:0;
                double D2=(i>=2&&j>=1)?dp[s-1][i-2][j-1]:0;
                double D3=(i>=2&&j<N-1)?dp[s-1][i-2][j+1]:0;
                double D4=(i>=1&&j<N-2)?dp[s-1][i-1][j+2]:0;
                double D5=(i<N-1&&j>=2)?dp[s-1][i+1][j-2]:0;
                double D6=(i<N-2&&j>=1)?dp[s-1][i+2][j-1]:0;
                double D7=(i<N-2&&j<N-1)?dp[s-1][i+2][j+1]:0;
                double D8=(i<N-1&&j<N-2)?dp[s-1][i+1][j+2]:0;
                dp[s][i][j]=(D1+D2+D3+D4+D5+D6+D7+D8)/8.0;
            }
    }
    double res=0; //这里的答案就是要求出最后一步，落在棋盘上各个位置上概率的总和
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++){
            res+=dp[K][i][j];
        }
    return res;
}

做完动态规划，可以很明显得看到，关于参数step即步数，关于它的每一个值，都依赖于前一次的值，那这里就可以进行一个空间的优化。考虑用一个pre数组记录前一个状态的dp数组，就可以将空间从三维压缩到2维。最终的代码如下：

class Solution {
public:
    double knightProbability(int P, int K, int i, int j) {
        size_t N=static_cast<size_t>(P);
        vector<vector<double>> dp(N,vector<double>(N,0));
        dp[i][j]=1;
        vector<vector<double>> pre;
        for(int k=0;k<K;k++){
            pre=dp;
            for(size_t i=0;i<N;i++)
                for(size_t j=0;j<N;j++){
                    double D1=(i>=1&&j>=2)?pre[i-1][j-2]:0;
                    double D2=(i>=2&&j>=1)?pre[i-2][j-1]:0;
                    double D3=(i>=2&&j<N-1)?pre[i-2][j+1]:0;
                    double D4=(i>=1&&j<N-2)?pre[i-1][j+2]:0;
                    double D5=(i<N-1&&j>=2)?pre[i+1][j-2]:0;
                    double D6=(i<N-2&&j>=1)?pre[i+2][j-1]:0;
                    double D7=(i<N-2&&j<N-1)?pre[i+2][j+1]:0;
                    double D8=(i<N-1&&j<N-2)?pre[i+1][j+2]:0;
                    dp[i][j]=(D1+D2+D3+D4+D5+D6+D7+D8)/8.0;
                }
        }
        double res=0;
        for(size_t i=0;i<N;i++)
            for(size_t j=0;j<N;j++){
                res+=dp[i][j];
            }
        return res;
    }
};