杭州模板网站制作,国外营销型网站,保定网络公司电话,网站制作公司哪里好#x1f600;前言 机器人移动问题是一个经典的动态规划应用场景#xff0c;它涉及到在给定范围内的位置上进行移动#xff0c;并计算到达目标位置的方法数。本文将介绍三种解决这一问题的方法#xff1a;暴力递归、缓存法和动态规划。通过比较不同方法的优缺点#xff0c;… 前言 机器人移动问题是一个经典的动态规划应用场景它涉及到在给定范围内的位置上进行移动并计算到达目标位置的方法数。本文将介绍三种解决这一问题的方法暴力递归、缓存法和动态规划。通过比较不同方法的优缺点我们将深入理解动态规划在解决问题中的重要性以及如何优化算法以提高性能和空间利用率。 个人主页尘觉主页 文章目录 动态规划--机器人移动问题Java机器人移动问题暴力递归缓存法动态规划 总结 动态规划–机器人移动问题Java
机器人移动问题
机器人可在1-N的位置上进行移动规定三个数据 分别是机器人当前位置 机器人可以移动的步数 机器人的目标位置 计算出机器人用光步数后到达目标位置的方法数
暴力递归
机器人在1-N的范围上进行移动一共会有3种情况
在1时只能右移动
在N时只能左移动
在中间时既可以左移又可以右移
所以可以根据这几种情况进行暴力递归
递归的终止条件是 当前步数为0 且处于目标位置上
public int moveTimes(int N,int cur,int target,int steps ){//三个参数分别是可以移动的范围 当前位置 目标位置if(steps0){//如果没有步数了进行返回return cur target?1:0;}if(cur1){return moveTimes(N,cur1,target,steps-1);}if (cur N){return moveTimes(N,cur-1,target,steps-1);}return moveTimes(N,cur1,target,steps-1) moveTimes(N,cur-1,target,steps-1);}缓存法
通过这种方式我们就可以取得最终的全部可能的情况但是显然我们的暴力递归会多做很对运算。比如当机器人处于中间位置的时当前的状态是 cur 5steps 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需要初始化所有值换成-1if(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,cur1,target,steps-1,cache);} else if(cur N){result moveTimes(N,cur-1,target,steps-1,cache);} else{result moveTimes(N,cur1,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[N1][steps1];//给第一列进行赋值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[j1][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[N1][steps1];//给第一列进行赋值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[j1][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(steps0){//如果没有步数了进行返回return cur target?1:0;}if(cur1){return moveTimes(N,cur1,target,steps-1);}if (cur N){return moveTimes(N,cur-1,target,steps-1);}return moveTimes(N,cur1,target,steps-1) moveTimes(N,cur-1,target,steps-1);}//傻缓存法public int moveTimes(int N,int cur,int target,int steps,int[][] cache){//cache需要初始化所有值换成-1if(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,cur1,target,steps-1,cache);} else if(cur N){result moveTimes(N,cur-1,target,steps-1,cache);} else{result moveTimes(N,cur1,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连支持一下创造不易您们的支持是我的动力
