2021-02-14：假設有排成一行的N個位置，記為1~N，N 一定大於或等於 2，開始時機器人在其中的M位置上(M 一定是 1~N 中的一個)。如果機器人來到1位置，那麼下一步只能往右來到2位置；如果機器人來到N位置，那麼下一步只能往左來到 N-1 位置；如果機器人來到中間位置，那麼下一步可以往左走或者往右走；規定機器人必須走 K 步，最終能來到P位置(P也是1~N中的一個)的方法有多少種？給定四個引數 N、M、K、P，返回方法數。

福哥答案2021-02-14：

自然智慧即可。

1.遞迴。有程式碼。

兩種情況。左移、右移。

2.帶dp的遞迴。有程式碼。

3.動態規劃。有程式碼。

dp[i][j]，i是機器人位置，j是剩餘步數。

dp[i][j]依賴左上和左下。見圖。

dp[i][j]=【左上】+【左下】。

4.另一種遞迴。有程式碼。

程式碼用golang編寫，程式碼如下：

package mainimport "fmt"func main() {    fmt.Println("1.遞迴：", RobotWalk1(5, 2, 4, 6))    fmt.Println("2.帶dp的遞迴：", RobotWalk2(5, 2, 4, 6))    fmt.Println("3.動態規劃：", RobotWalk3(5, 2, 4, 6))    fmt.Println("4.另一種遞迴：", RobotWalk4(5, 2, 4, 6))}func RobotWalk1(N int, start int, aim int, K int) int {    if N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1 {        return -1    }    return process1(start, K, aim, N)}// 機器人當前來到的位置是cur，// 機器人還有rest步需要去走，// 最終的目標是aim，// 有哪些位置？1~N// 返回：機器人從cur出發，走過rest步之後，最終停在aim的方法數，是多少？func process1(cur int, rest int, aim int, N int) int {    if rest == 0 { // 如果已經不需要走了，走完了！        if cur == aim {            return 1        } else {            return 0        }    }    // (cur, rest)    if cur == 1 { // 1 -> 2        return process1(2, rest-1, aim, N)    }    // (cur, rest)    if cur == N { // N-1 <- N        return process1(N-1, rest-1, aim, N)    }    // (cur, rest)    return process1(cur-1, rest-1, aim, N) + process1(cur+1, rest-1, aim, N)}func RobotWalk2(N int, start int, aim int, K int) int {    if N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1 {        return -1    }    dp := make([][]int, N+1)    for i := 0; i < N+1; i++ {        dp[i] = make([]int, K+1)    }    for i := 0; i <= N; i++ {        for j := 0; j <= K; j++ {            dp[i][j] = -1        }    }    // dp就是快取表    // dp[cur][rest] == -1 -> process1(cur, rest)之前沒算過！    // dp[cur][rest] != -1 -> process1(cur, rest)之前算過！返回值，dp[cur][rest]    // N+1 * K+1    return process2(start, K, aim, N, dp)}// cur 範: 1 ~ N// rest 範：0 ~ Kfunc process2(cur int, rest int, aim int, N int, dp [][]int) int {    if dp[cur][rest] != -1 {        return dp[cur][rest]    }    // 之前沒算過！    ans := 0    if rest == 0 {        if cur == aim {            ans = 1        } else {            ans = 0        }    } else if cur == 1 {        ans = process2(2, rest-1, aim, N, dp)    } else if cur == N {        ans = process2(N-1, rest-1, aim, N, dp)    } else {        ans = process2(cur-1, rest-1, aim, N, dp) + process2(cur+1, rest-1, aim, N, dp)    }    dp[cur][rest] = ans    return ans}func RobotWalk3(N int, start int, aim int, K int) int {    if N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1 {        return -1    }    dp := make([][]int, N+1)    for i := 0; i < N+1; i++ {        dp[i] = make([]int, K+1)    }    dp[aim][0] = 1    for rest := 1; rest <= K; rest++ {        dp[1][rest] = dp[2][rest-1]        for cur := 2; cur < N; cur++ {            dp[cur][rest] = dp[cur-1][rest-1] + dp[cur+1][rest-1]        }        dp[N][rest] = dp[N-1][rest-1]    }    return dp[start][K]}//遞迴func RobotWalk4(N int, start int, aim int, K int) int {    ansVal := 0    ans := &ansVal    process4(N, start, K, aim, ans)    return *ans}//N個位置，固定//M是起始位置//K步//P是最終位置，固定func process4(N int, M int, K int, P int, ans *int) {    if M < 1 || M > N {        return    }    if K == 0 {        if M == P {            *ans++        }        return    }    process4(N, M-1, K-1, P, ans)    process4(N, M+1, K-1, P, ans)}

執行結果如下：

***

[左神java程式碼](https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class18/Code01_RobotWalk.java)