问题描述

想象一个象棋的棋盘，然后把整个棋盘放入第一象限，棋盘的最左下角是 (0,0) 位置。那么整个棋盘就是横坐标上 9 条线、纵坐标上 10 条线的区域。给你三个参数 x，y，k，返回马从 (0,0) 位置出发，必须走 k 步，最后落在 (x,y) 上的方法有多少种?

暴力递归

问题类型和之前的机器人行走问题类似，只不过这里的行走方式扩展成了二维，但基本处理思路依然不变。

对于之前的机器人行走，每一个位置需要分别尝试向左和向右走；而此处马的尝试方向则有 8 种（马走“日”字）：

所以在每个位置上我们依次尝试这 8 个方向，并将结果相加并返回即可，代码如下：

//x,y为当前坐标
//a,b为目的地坐标
//rest为剩余可走步数
int process(int x, int y, int rest, int a, int b)
{
    if (x < 0 || x > 9 || y < 0 || y > 8)//越界处理
        return 0;
    if (rest == 0)
    {
        if(x == a && y == b)
            return 1;
        else
            return 0;
    }
    int ways = 0;
    ways += process(x + 2, y + 1, rest - 1, a, b);
    ways += process(x + 1, y + 2, rest - 1, a, b);
    ways += process(x - 1, y + 2, rest - 1, a, b);
    ways += process(x - 2, y + 1, rest - 1, a, b);
    ways += process(x - 2, y - 1, rest - 1, a, b);
    ways += process(x - 1, y - 2, rest - 1, a, b);
    ways += process(x + 1, y - 2, rest - 1, a, b);
    ways += process(x + 2, y - 1, rest - 1, a, b);
    return ways;
}
//====================================================================
int horseWalk(int x, int y, int steps)
{
    return process(0, 0, steps, x, y);
}

解题思路完全同机器人行走，不再赘述。

动态规划

容易知道 x、y、rest 为状态变量，故创建一个三维数组作为 dp 表。注意，rest 剩余步数可以为 0 ，所以下面代码中开辟空间必须为 k+1 。

上面的递归版本中，我们是在下游处理越界情况，上游只管传入方向，当越界时下游直接向上游传回 0 表示无路可走，这样做比在上游判断越界更方便简洁。而动态规划时，越界处理则只能在上游（将坐标传给数组前）进行。 如果每次从 dp 表中取值时都判断越界情况，则代码显得重复臃肿，所以下面代码中我们使用 pick 函数来进行越界判断和取值。

int pick(vector<vector<vector<int>>> &dp, int x, int y, int rest)
{
    if (x < 0 || x > 9 || y < 0 || y > 8)
        return 0;
    return dp[x][y][rest];
}
int dp(int a, int b, int k) 
{
    vector<vector<vector<int>>> dp(10, vector<vector<int>>(9, vector<int>(k + 1, 0)));//注意是k+1
    dp[a][b][0] = 1;
    for (int rest = 1; rest <= k; rest++) 
    {
        for (int x = 0; x < 10; x++) 
        {
            for (int y = 0; y < 9; y++) 
            {
                int ways = pick(dp, x + 2, y + 1, rest - 1);
                ways += pick(dp, x + 1, y + 2, rest - 1);
                ways += pick(dp, x - 1, y + 2, rest - 1);
                ways += pick(dp, x - 2, y + 1, rest - 1);
                ways += pick(dp, x - 2, y - 1, rest - 1);
                ways += pick(dp, x - 1, y - 2, rest - 1);
                ways += pick(dp, x + 1, y - 2, rest - 1);
                ways += pick(dp, x + 2, y - 1, rest - 1);
                dp[x][y][rest] = ways;
            }
        }
    }
    return dp[0][0][k];
}
int horseWalk(int x, int y, int steps)
{
    return dp(x, y, steps);
}

总结

• 动态规划从 dp 表中取值时须提前处理越界情况。
• 本题中三维表的位置依赖并不复杂，但有些题目中如果使用三维表，位置依赖则眼花缭乱。因此状态变量能少则少。