上一题比较简单，下面来一道比较难的题目。

假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2

开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)

如果机器人来到1位置，那么下一步只能往右来到2位置；

如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；

如果机器人来到中间位置，那么下一步可以往左走或者往右走；

规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种

给定四个参数 N、M、K、P，返回方法数。

解题思路：

1. 如果机器人在1的位置，只能从左到右

2.如果机器人在N的位置，只能从右到左

3.如果机器人在中间，既可以往右、也可以往左

现在的题目是要求返回多少种走法，也就是只要能到达目的地，并且步数足够，我们随意走都可以。

遇到这种题目，绘图是最好的方式：

假设一共有6个位置，从2位置出发，走5步，到达位置5，一共有多少种走法

 

递归方式 

package code03.动态规划_07;/*** 假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2* 开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)* 如果机器人来到1位置，那么下一步只能往右来到2位置；* 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；* 如果机器人来到中间位置，那么下一步可以往左走或者往右走；* 规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种* 给定四个参数 N、M、K、P，返回方法数。*/
public class Robot_02 {/**** @param mStart   M 开始位置* @param kSteps   K 步数* @param nAll     N 长度* @param pAim     P 目的地位置* @return*/public static int way1(int mStart, int kSteps, int nAll, int pAim){return process(mStart, kSteps, nAll, pAim);}public static int process ( int mStart, int kSteps, int nAll, int pAim){//步数为0，没法走if (kSteps == 0) {return mStart == pAim ? 1 : 0;}//只能往右走if (mStart == 1) {return process(mStart + 1, kSteps-1, nAll, pAim);}//只能往左走if (mStart == nAll) {return process(nAll-1, kSteps-1, nAll, pAim);}//中间位置，即可往左，也可往右，需要统计出往左往右的和return process(mStart +1, kSteps-1, nAll, pAim)+  process( mStart -1, kSteps-1, nAll, pAim);}public static void main(String[] args) {System.out.println(way1(2,5,6,5));}
}

同样的问题，我们分析可以得到：

在2位置，剩余5步，有5中走法

在3位置，剩余4步，有4种走法

在4位置，剩余3步，有3种走法

在5位置，剩余2步，有2种走法；

在6位置，剩余1步，有1种走法

中间存在来来回回重复的走法，这说明我们存在重复的推导结果，自然就过渡到递归+动态规划的方式进行优化了。

递归 + 动态规划

package code03.动态规划_07;/*** 假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2* 开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)* 如果机器人来到1位置，那么下一步只能往右来到2位置；* 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；* 如果机器人来到中间位置，那么下一步可以往左走或者往右走；* 规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种* 给定四个参数 N、M、K、P，返回方法数。*/
public class Robot_02_opt1 {/*** @param mStart   M 开始位置  [0-nAll]* @param kSteps   K 步数* @param nAll     N 长度* @param pAim     P 目的地位置* @return*/public static int way1(int mStart, int kSteps, int nAll, int pAim){/*** 位置是1-N, 每一个位置都存在不同的走法，以每个位置为行，那么行的范围就是1-N* 由于java数组下标从0开始，想要获取1-N范围，长度需要加1** 我们将剩余步数为列，这样每个位置剩余步数就可以很直观的观察到*/int[][] dp = new int[nAll + 1][kSteps+1]; //剩余步数为横坐标，当前位置为纵坐标for (int i = 0; i < dp.length; i++) {for(int j = 0; j <dp[i].length; j++) {dp[i][j] = -1;}}int result = process(mStart, kSteps, nAll, pAim, dp);return process(mStart, kSteps, nAll, pAim, dp);}public static int process ( int mStart, int kSteps, int nAll, int pAim, int[][] dp){if (dp[mStart][kSteps] != -1) {return dp[mStart][kSteps];}int result;if (kSteps == 0) {result = mStart == pAim ? 1 : 0;}//只能往右走else if (mStart == 1) {result =  process(mStart + 1, kSteps-1, nAll, pAim, dp);}//只能往左走else if (mStart == nAll) {result = process(nAll-1, kSteps-1, nAll, pAim, dp);}//中间位置，即可往左，也可往右，需要统计出往左往右的和else{result = process(mStart +1, kSteps-1, nAll, pAim, dp)+  process( mStart -1, kSteps-1, nAll, pAim, dp);}dp[mStart][kSteps] = result;return result;}public static void main(String[] args) {System.out.println(way1(2,5,6,5));}
}

纯动态规划方式

1. 根据递归的方式，我们知道，如果剩余步数为0，那么开始位置如果正好在目标位置处，就算是1种走法。并且可以推导二维数组的第一列，第五行为1，其他都为0

if (kSteps == 0) {return mStart == pAim ? 1 : 0;
}

x	x	x	x	x	x
0
0
0
0
1
0

2. 根据递归方式，如果在最左端，只能往右走; 如果在最右端，只能往左走。目前第一列数据已经推导出来了。因此需要根据第一列进行推导。

//只能往右走
if (mStart == 1) {return process(mStart + 1, kSteps-1, nAll, pAim);
}
//只能往左走
if (mStart == nAll) {return process(nAll-1, kSteps-1, nAll, pAim);
}

根据递归代码，我们知道，无论是往左走，还是往右走。

第二行第二列，也就是dp[1][1],  都是下一行的前一列数据. 而最后一行最后一列，都是上一行前一列的数据。推导结果》

x	x	x	x	x	x
0	0
0
0
0
1
0	1

3. 根据递归方法中，如果在中间位置。需要得到上一行和下一行的前一列累加值

//中间位置，即可往左，也可往右，需要统计出往左往右的和
return process(mStart +1, kSteps-1, nAll, pAim)+  process( mStart -1, kSteps-1, nAll, pAim);

推导出结果

x	x	x	x	x	x
0	0
0	0
0	0
0	1
1	0
0	1

依次类推，得到的最终值为：

	剩余0	剩余1	剩余2	剩余3	剩余4	剩余5
目标位置0	x	x	x	x	x	x
目标位置1	0	0	0	0	1	0
目标位置2	0	0	0	1	0	5
目标位置3	0	0	1	0	4	0
目标位置4	0	1	0	3	0	9
目标位置5	1	0	2	0	5	0
目标位置6	0	1	0	2	0	9

根据题目我们知道，位置是从1到N的，也就是说位置不存在0的情况。而我们这张表位置作为行，剩余步数作为列的。因此位置为0直接忽略。

假设一共有6个位置，从2位置出发，走5步，到达位置5，一共有多少种走法

dp[2][5]可得到结果为5，即5中种走法。

package code03.动态规划_07;/*** 假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2* 开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)* 如果机器人来到1位置，那么下一步只能往右来到2位置；* 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；* 如果机器人来到中间位置，那么下一步可以往左走或者往右走；* 规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种* 给定四个参数 N、M、K、P，返回方法数。*/
public class Robot_02_opt2 {/**** @param mStart   M 开始位置* @param kSteps   K 步数* @param nAll     N 长度* @param pAim     P 目的地位置* @return*/public static int way(int nAll, int mStart, int pAim, int kSteps){if (nAll < 2 || mStart < 1 || mStart > nAll || pAim < 1 || pAim > nAll || kSteps < 1) {return -1;}/*** 位置是1-N, 每一个位置都存在不同的走法，以每个位置为行，那么行的范围就是1-N* 由于java数组下标从0开始，想要获取1-N范围，长度需要加 1** 我们将剩余步数为列，这样每个位置剩余步数就可以很直观的观察到.* 同理，列的长度也需要加 1。** 其实，此处列无所谓的，哪怕就是100也行。只不过如果是100，那将会推导出* 走100的情况，无谓浪费资源。 最好的方式就是根据实际的业务，你要我推导* 几步，我就推导几步，节约资源*/int[][] dp = new int[nAll+1][kSteps+1];//剩余步数为0，推导出对应哪一行为1dp[pAim][0] = 1;//根据剩余步数，推导出每一个位置能够走到目标位置的结果for (int col = 1; col <= kSteps; col++){//第2行的每一列值, 对应的都是第3行前一列值dp[1][col] = dp[2][col-1];//从第二行开始，倒数第二行执行完后结束for (int row = 2; row < nAll; row++){//中间行，等于上一行和下一行的前一列的和dp[row][col] = dp[row-1][col-1] + dp[row+1][col-1];}//最后一行，每一列值都对应上一行的前一列的值dp[nAll][col] = dp[nAll-1][col-1];}//根据当前哪个位置，剩余步数。获取到目标位置的不同走法return dp[mStart][kSteps];}public static void main(String[] args) {System.out.println(way(6,2,5,5));}
}