动态规划—机器人移动问题（Java）

😀前言
机器人移动问题是一个经典的动态规划应用场景，它涉及到在给定范围内的位置上进行移动，并计算到达目标位置的方法数。本文将介绍三种解决这一问题的方法：暴力递归、缓存法和动态规划。通过比较不同方法的优缺点，我们将深入理解动态规划在解决问题中的重要性以及如何优化算法以提高性能和空间利用率。

🏠个人主页：尘觉主页

动态规划–机器人移动问题（Java）

机器人移动问题

机器人可在1-N的位置上进行移动，规定三个数据 分别是机器人当前位置 机器人可以移动的步数 机器人的目标位置 计算出机器人用光步数后到达目标位置的方法数

暴力递归

机器人在1-N的范围上进行移动，一共会有3种情况，

在1时，只能右移动

在N时，只能左移动

在中间时，既可以左移，又可以右移；

所以可以根据这几种情况进行暴力递归

递归的终止条件是 当前步数为0 且处于目标位置上

public int moveTimes(int N,int cur,int target,int steps ){//三个参数分别是可以移动的范围 当前位置 目标位置if(steps==0){//如果没有步数了进行返回return cur == target?1:0;}if(cur==1){return moveTimes(N,cur+1,target,steps-1);}if (cur == N){return moveTimes(N,cur-1,target,steps-1);}return moveTimes(N,cur+1,target,steps-1) + moveTimes(N,cur-1,target,steps-1);}

缓存法

通过这种方式我们就可以取得最终的全部可能的情况，但是显然，我们的暴力递归，会多做很对运算。比如当机器人处于中间位置的时，当前的状态是 cur = 5，steps = 10 那么在接下来的递归中我们会有这样的2个分支

​ （4,9）-> （5,8）/ （3,8） | （6,9）-> (5,8)/（7,8）

那么我们的（5,8）在计算过一次之后，还会再次进行计算。这样的情况下，我们的运行时间就会变得过长 。

所以我们引出了傻缓存法，缓存的作用在于，我们进行一次递归的过程中，便将这一次递归的结果记录到缓存中，当下一次再次递归时，可以直接调用之前在缓存中数，进行返回，而不是继续向下递归了，这种方法就是再用时间来换空间！

那么回到这道题，我们的cache就可以用一个二维数组来进行存储，row为我们的当前位置 col 为我们的可移动步数

//傻缓存法public int moveTimes(int N,int cur,int target,int steps,int[][] cache){//cache需要初始化；所有值换成-1；if(cache[cur][steps]!=-1){return cache[cur][steps];}int result = -1;//分3种情况进行递归移动//basecaseif (steps == 0){result = cur == target?1:0;} else if (cur == 1){result = moveTimes(N,cur+1,target,steps-1,cache);} else if(cur == N){result = moveTimes(N,cur-1,target,steps-1,cache);} else{result = moveTimes(N,cur+1,target,steps-1,cache)+moveTimes(N,cur-1,target,steps-1,cache);}cache[cur][steps] = result;return result;}public void setCache(int[][] cache){for (int i = 0; i < cache.length; i++) {for (int j = 0; j < cache[1].length; j++) {cache[i][j] = -1;}}}

这里相比第一种方式会更快一些，但是也是浪费了较大的空间；

动态规划

我们结合一二一起看，会发现我们能basecase的情况发生时，可以在缓存即二维数组中确定一些数，当 step = 0时，在二维数组中这一列，我们除了是目标位置会返回 1 以外，其他位置都会返回 0 。所以我们就可以把确定的数据填写到二维数组中，在看暴力递归的其他情况，当我们在第 1 行的时候 ，只能向右移动，所以我们的返回值，要从相对于二维数组中的当前位置的左下角中的这个元素获取返回值，同理当我们在最后 1 行的时候，那么就应该从当前位置的左上角进行取返回值了，当我们在中间位置的时候，我们的则是需要从左上和左下相加来获取返回值，依次类推，我们会回到我们最开始的位置，这时就是我们需要的结果了。

    public int moveTimes1(int N,int cur,int target,int steps){int[][] cache = new int[N+1][steps+1];//给第一列进行赋值cache[target][0] = 1;for (int i = 1; i <= steps; i++) {//第一行手动操作cache[1][i] = cache[2][i-1];for (int j = 2; j <= N-1 ; j++) {cache[j][i] = cache[j+1][i-1]+cache[j-1][i-1];}cache[N][i] = cache[N-1][i-1];}return cache[cur][steps];}

完整的代码

@SuppressWarnings({"all"})
public class Robot {//测试public static void main(String[] args) {Robot robot = new Robot();int[][] cache = new int[6][6];robot.setCache(cache);System.out.println(robot.moveTimes(5, 2, 3, 5, cache));System.out.println(robot.moveTimes(5,2,3,5));System.out.println(robot.moveTimes1(5,2,3,5));}//动态规划法public int moveTimes1(int N,int cur,int target,int steps){int[][] cache = new int[N+1][steps+1];//给第一列进行赋值cache[target][0] = 1;for (int i = 1; i <= steps; i++) {//第一行手动操作cache[1][i] = cache[2][i-1];for (int j = 2; j <= N-1 ; j++) {cache[j][i] = cache[j+1][i-1]+cache[j-1][i-1];}cache[N][i] = cache[N-1][i-1];}return cache[cur][steps];}//暴力递归法public int moveTimes(int N,int cur,int target,int steps ){//三个参数分别是可以移动的范围 当前位置 目标位置if(steps==0){//如果没有步数了进行返回return cur == target?1:0;}if(cur==1){return moveTimes(N,cur+1,target,steps-1);}if (cur == N){return moveTimes(N,cur-1,target,steps-1);}return moveTimes(N,cur+1,target,steps-1) + moveTimes(N,cur-1,target,steps-1);}//傻缓存法public int moveTimes(int N,int cur,int target,int steps,int[][] cache){//cache需要初始化；所有值换成-1；if(cache[cur][steps]!=-1){return cache[cur][steps];}int result = -1;//分3种情况进行递归移动//basecaseif (steps == 0){result = cur == target?1:0;} else if (cur == 1){result = moveTimes(N,cur+1,target,steps-1,cache);} else if(cur == N){result = moveTimes(N,cur-1,target,steps-1,cache);} else{result = moveTimes(N,cur+1,target,steps-1,cache)+moveTimes(N,cur-1,target,steps-1,cache);}cache[cur][steps] = result;return result;}public void setCache(int[][] cache){for (int i = 0; i < cache.length; i++) {for (int j = 0; j < cache[1].length; j++) {cache[i][j] = -1;}}}
}

😄总结

通过本文的学习，我们了解了三种解决机器人移动问题的方法：暴力递归、缓存法和动态规划。暴力递归虽然简单易懂，但效率低下；缓存法通过牺牲空间来换取时间，提高了效率；而动态规划则利用填充二维数组的方式，避免了重复计算，进一步优化了性能和空间利用率。动态规划在解决各种问题中都有广泛的应用，是一种重要的算法思想。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞