2021-02-22：一個象棋的棋盤，然后把整個棋盤放入第一象限，棋
2021-02-22：一個象棋的棋盤，然后把整個棋盤放入第一象限，棋盤的最左下角是(0,0)位置，那么整個棋盤就是橫坐標上9條線、縱坐標上10條線的區(qū)域。給你三個 參數(shù) x，y，k。返回“馬”從(0,0)位置出發(fā)，必須走k步。最后落在(x,y)上的方法數(shù)有多少種??
福哥答案2021-02-22：
自然智慧即可。
1.遞歸。有代碼。
2.記憶化搜索。有代碼。
3.動態(tài)規(guī)劃。dp是三維數(shù)組。棋盤是二維數(shù)組，走k步，需要k+1個棋盤。有代碼。
4.動態(tài)規(guī)劃，空間壓縮。只有相鄰棋盤才有依賴，所以只需要用兩個棋盤，就能走完。有代碼。
代碼用golang編寫，代碼如下：
```go
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.動態(tài)規(guī)劃：", jump3(a, b, k))
? ? fmt.Println("---")
? ? fmt.Println("4.動態(tài)規(guī)劃,空間壓縮：", 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]
}
```
執(zhí)行結(jié)果如下：
***
[左神java代碼](https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class20/Code02_HorseJump.java)
[評論](https://user.qzone.qq.com/3182319461/blog/1613948266)
