上一题比较简单，下面来一道比较难的题目。
假设有排成一行的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，一共有多少种走法文章来源：https://www.toymoban.com/news/detail-494035.html
dp[2][5]可得到结果为5，即5中种走法。文章来源地址https://www.toymoban.com/news/detail-494035.html
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，推导出对应哪一行为1
dp[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));
}
}
到了这里，关于算法27：从暴力递归到动态规划（2）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
