機器人達到指定位置方法數

來自左程云老師書中的一道題

【題目】

假設有排成一行的 N 個位置，記為 1~N，N 一定大于或等于 2。開始時機器人在其中的 M

位置上（M 一定是 1～N 中的一個），機器人可以往左走或者往右走，如果機器人來到 1 位置，

那么下一步只能往右來到 2 位置；如果機器人來到 N 位置，那么下一步只能往左來到 N-1 位置。

規定機器人必須走 K 步，最終能來到 P 位置（P 也一定是 1～N 中的一個）的方法有多少種。給

定四個參數 N、M、K、P，返回方法數。

【舉例】

N=5,M=2,K=3,P=3

上面的參數代表所有位置為 1 2 3 4 5。機器人最開始在 2 位置上，必須經過 3 步，最后到

達 3 位置。走的方法只有如下 3 種：

1）從 2 到 1，從 1 到 2，從 2 到 3

2）從 2 到 3，從 3 到 2，從 2 到 3

3）從 2 到 3，從 3 到 4，從 4 到 3

所以返回方法數 3。

N=3,M=1,K=3,P=3

上面的參數代表所有位置為 1 2 3。機器人最開始在 1 位置上，必須經過 3 步，最后到達 3

位置。怎么走也不可能，所以返回方法數 0。

遞歸代碼:

public static int process(int N,int M,int K, int P) {if(K == 0) {return M == P? 1:0;}if(M ==1) {return process(N,M+1,K-1,P);}if(M == N) {return process(N,M-1,K-1,P);}return process(N,M+1,K-1,P) + process(N,M-1,K-1,P);}

遞歸推導動態規劃

前提：判斷是否是無后效性的。所謂無后效性是指是指一個遞歸狀態的返回值與怎么到達這個狀態的路徑無關。

1. 找到什么可變參數可以代表一個遞歸狀態，也就是那些參數一旦確定，返回值也就確定了
2. 把可變參數的所有組合映射成一張表，有1個可變參數就是一維表，有2個可變參數就是一張二維表….
3. 最終答案要的是表中哪個位置，在表中標出。
4. 根據遞歸的base case ，把這張表最簡單、不需要依賴其他位置的那些位置填好
5. 根據遞歸過程非base case的部分，也就是分析表中的普遍位置需要怎么計算得到，那么這張表的填寫順序也就確定了
6. 填好表，返回最終答案在表中位置的值。

動態規劃代碼：

public static int process2(int N,int M,int K, int P) {int[][] dp = new int[K+1][N+1];dp[0][P] = 1;for(int i =1;i<=K;i++) {for(int j=1;j<=N;j++) {if(j==1) {dp[i][j] = dp[i-1][j+1];} else if(j == N) {dp[i][j] = dp[i-1][j-1];} else {dp[i][j] =  dp[i-1][j+1] + dp[i-1][j-1];}}}return dp[K][M];}