关于福大大架构师每日一题:20210222一个象棋的棋盘然后把整个棋盘放入第一象限棋盘的最左下角是00位置

2021-02-22：一个象棋的棋盘，而后把整个棋盘放入第一象限，棋盘的最左下角是 (0,0) 地位，那么整个棋盘就是横坐标上 9 条线、纵坐标上 10 条线的区域。给你三个 参数 x，y，k。返回“马”从 (0,0) 地位登程，必须走 k 步。最初落在 (x,y) 上的办法数有多少种?
福哥答案 2021-02-22：

天然智慧即可。
1. 递归。有代码。
2. 记忆化搜寻。有代码。
3. 动静布局。dp 是三维数组。棋盘是二维数组，走 k 步，须要 k + 1 个棋盘。有代码。
4. 动静布局，空间压缩。只有相邻棋盘才有依赖，所以只须要用两个棋盘，就能走完。有代码。

代码用 golang 编写，代码如下：

package main

import "fmt"

func main() {

    a := 3
    b := 4
    k := 5
    fmt.Println("1. 递归：", jump1(a, b, k))
    fmt.Println("---")
    fmt.Println("2. 记忆化搜寻：", jump2(a, b, k))
    fmt.Println("---")
    fmt.Println("3. 动静布局：", jump3(a, b, k))
    fmt.Println("---")
    fmt.Println("4. 动静布局, 空间压缩：", jump4(a, b, k))
}

func jump1(a int, b int, k int) int {return process1(0, 0, k, a, b)
}
func process1(x int, y int, rest int, a int, b int) int {
    if x < 0 || x >= 9 || y < 0 || y >= 10 {return 0}
    if rest == 0 {
        if x == a && y == b {return 1} else {return 0}
    }
    ways := process1(x+2, y+1, rest-1, a, b)
    ways += process1(x+2, y-1, rest-1, a, b)
    ways += process1(x-2, y+1, rest-1, a, b)
    ways += process1(x-2, y-1, rest-1, a, b)
    ways += process1(x+1, y+2, rest-1, a, b)
    ways += process1(x+1, y-2, rest-1, a, b)
    ways += process1(x-1, y+2, rest-1, a, b)
    ways += process1(x-1, y-2, rest-1, a, b)
    return ways
}

func jump2(a int, b int, k int) int {dp := make([][][]int, 10)
    for i := 0; i < 10; i++ {dp[i] = make([][]int, 9)
        for j := 0; j < 9; j++ {dp[i][j] = make([]int, k+1)
            for m := 0; m < k+1; m++ {dp[i][j][m] = -1
            }
        }
    }
    return process2(0, 0, k, a, b, dp)
}
func process2(x int, y int, rest int, a int, b int, dp [][][]int) int {
    if x < 0 || x >= 10 {return 0}
    if y < 0 || y >= 9 {return 0}
    if dp[x][y][rest] != -1 {return dp[x][y][rest]
    }
    if rest == 0 {
        if x == a && y == b {dp[x][y][rest] = 1
            return 1
        } else {dp[x][y][rest] = 0
            return 0
        }
    }
    ways := process2(x+2, y+1, rest-1, a, b, dp)
    ways += process2(x+2, y-1, rest-1, a, b, dp)
    ways += process2(x-2, y+1, rest-1, a, b, dp)
    ways += process2(x-2, y-1, rest-1, a, b, dp)
    ways += process2(x+1, y+2, rest-1, a, b, dp)
    ways += process2(x+1, y-2, rest-1, a, b, dp)
    ways += process2(x-1, y+2, rest-1, a, b, dp)
    ways += process2(x-1, y-2, rest-1, a, b, dp)
    dp[x][y][rest] = ways
    return ways

}

func jump3(a int, b int, k int) int {dp := make([][][]int, 10)
    for i := 0; i < 10; i++ {dp[i] = make([][]int, 9)
        for j := 0; j < 9; j++ {dp[i][j] = make([]int, k+1)
        }
    }
    dp[a][b][0] = 1
    for rest := 1; rest <= k; rest++ {
        for x := 0; x < 10; x++ {
            for y := 0; y < 9; y++ {ways := pick3(x+2, y+1, rest-1, dp)
                ways += pick3(x+1, y+2, rest-1, dp)
                ways += pick3(x-1, y+2, rest-1, dp)
                ways += pick3(x-2, y+1, rest-1, dp)
                ways += pick3(x-2, y-1, rest-1, dp)
                ways += pick3(x-1, y-2, rest-1, dp)
                ways += pick3(x+1, y-2, rest-1, dp)
                ways += pick3(x+2, y-1, rest-1, dp)
                dp[x][y][rest] = ways
            }
        }
    }
    return dp[0][0][k]
}
func pick3(x int, y int, rest int, dp [][][]int) int {
    if x < 0 || x >= 10 || y < 0 || y >= 9 {return 0}
    return dp[x][y][rest]
}

func jump4(a int, b int, k int) int {dp := make([][][]int, 10)
    for i := 0; i < 10; i++ {dp[i] = make([][]int, 9)
        for j := 0; j < 9; j++ {dp[i][j] = make([]int, 2)
        }
    }
    dp[a][b][0] = 1
    for rest := 1; rest <= k; rest++ {
        for x := 0; x < 10; x++ {
            for y := 0; y < 9; y++ {ways := pick4(x+2, y+1, dp)
                ways += pick4(x+1, y+2, dp)
                ways += pick4(x-1, y+2, dp)
                ways += pick4(x-2, y+1, dp)
                ways += pick4(x-2, y-1, dp)
                ways += pick4(x-1, y-2, dp)
                ways += pick4(x+1, y-2, dp)
                ways += pick4(x+2, y-1, dp)
                dp[x][y][1] = ways
            }
        }
        for i := 0; i < 10; i++ {
            for j := 0; j < 9; j++ {dp[i][j][0], dp[i][j][1] = dp[i][j][1], 0
            }
        }
    }
    return dp[0][0][0]
}
func pick4(x int, y int, dp [][][]int) int {
    if x < 0 || x >= 10 || y < 0 || y >= 9 {return 0}
    return dp[x][y][0]
}

执行后果如下：

左神 java 代码
评论