当前位置: 首页 > news >正文

动态规划—机器人移动问题(Java)

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

🏠个人主页:尘觉主页

文章目录

  • 动态规划--机器人移动问题(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连支持一下,创造不易您们的支持是我的动力🤞

相关文章:

动态规划—机器人移动问题(Java)

&#x1f600;前言 机器人移动问题是一个经典的动态规划应用场景&#xff0c;它涉及到在给定范围内的位置上进行移动&#xff0c;并计算到达目标位置的方法数。本文将介绍三种解决这一问题的方法&#xff1a;暴力递归、缓存法和动态规划。通过比较不同方法的优缺点&#xff0c;…...

第十一届蓝桥杯物联网试题(省赛)

对于通信方面&#xff0c;还是终端A、B都保持接收状态&#xff0c;当要发送的数组不为空再发送数据&#xff0c;发送完后立即清除&#xff0c;接收数据的数组不为空则处理&#xff0c;处理完后立即清除&#xff0c;分工明确 继电器不亮一般可能是电压不够 将数据加空格再加\r…...

【Python基础教程】5. 数

&#x1f388;个人主页&#xff1a;豌豆射手^ &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;python基础教程 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、…...

Qt中出现中文乱码的原因以及解决方法

Qt专栏&#xff1a;http://t.csdnimg.cn/C2SDN 目录 1.引言 2.原因分析 3.源文件的编码格式修改方法 4.程序内部使用的默认编码格式修改方法 5.QString转std::string的方法 6.总结 1.引言 在编写Qt程序的时候&#xff0c;或多或少都可能遇到用QString时候&#xff0c;明明…...

Linux 文件相关命令

一、查看文件命令 1&#xff09;浏览文件less 默认查看文件的前 10 行。 less /etc/services ##功能说明&#xff1a; #1.默认打开首屏内容 #2.按【回车】按行访问 #3.按【空格】按屏访问 #4.【从上向下】搜索用/111,搜索包含111的内容&#xff0c;此时按n继续向下搜&#x…...

K8S Deployment 简介, 1个简单的Kubernetes Deployment YAML 文件

当谈到 Kubernetes 集群中的应用程序部署和管理时&#xff0c;Deployment、ReplicaSet 和 Pod 是三个重要的概念。它们之间存在一定的关系和层次结构。下面是对 Deployment、ReplicaSet 和 Pod 的详细解释以及它们之间的关系。 Deployment&#xff08;部署&#xff09; Deploy…...

win11安装WSL UbuntuTLS

win11安装WSL WSL 简介WSL 1 VS WSL 2先决要求安装方法一键安装通过「控制面板」安装 WSL 基本命令Linux发行版安装Ubuntu初始化相关设置root用户密码网络工具安装安装1panel面板指导 WSl可视化工具问题总结WSL更新命令错误Ubuntu 启动初始化错误未解决问题 WSL 简介 Windows …...

第十题:金币

题目描述 国王将金币作为工资&#xff0c;发放给忠诚的骑士。第一天&#xff0c;骑士收到一枚金币&#xff1b;之后两天&#xff08;第二天和第三天&#xff09;&#xff0c;每天收到两枚金币&#xff1b;之后三天&#xff08;第四、五、六天&#xff09;&#xff0c;每天收到…...

Windows 11 中Docker的安装教程

选择正确的Docker版本 在Windows上&#xff0c;你可以安装两种类型的Docker&#xff1a;Docker Desktop和Docker Toolbox。Docker Desktop是针对Windows 10 Pro、Enterprise和Education版本的&#xff0c;这些版本内置了Hyper-V虚拟化支持。对于旧版本的Windows&#xff0c;比…...

纯C代码模板

一、快排 void QuickSort(int *a,int left,int right){if(left>right) return;else{int low left,high right;int pivot a[low];while(low<high){while(a[high] > pivot && low < high){high--;}a[low] a[high]; //必须先动a[low]while(a[low] < …...

二、GitLab相关操作

GitLab相关操作 一、组、用户、项目管理1.创建组2.创建项目3.创建用户并分配组3.1 创建用户3.2 设置密码3.3 给用户分配组 二、拉取/推送代码1.配置ssh(第一次需要)1.1 创建一个空文件夹1.2 配置本地仓账号和邮箱1.3 生成ssh公钥密钥1.4 gitlab配置公钥 2.拉取代码3.推送代码3.…...

【详细注释+流程讲解】基于深度学习的文本分类 TextCNN

前言 这篇文章用于记录阿里天池 NLP 入门赛&#xff0c;详细讲解了整个数据处理流程&#xff0c;以及如何从零构建一个模型&#xff0c;适合新手入门。 赛题以新闻数据为赛题数据&#xff0c;数据集报名后可见并可下载。赛题数据为新闻文本&#xff0c;并按照字符级别进行匿名…...

Day.21

interface MyInterface{public final static int PI 3;void show();public default void printX(){System.out.println("接口默认方法");}public static void printY(){System.out.println("接口静态方法");}}class MyClass implements MyInterface{publi…...

Spring-IoC 基于注解

基于xml方法见&#xff1a;http://t.csdnimg.cn/dir8j 注解是代码中的一种特殊标记&#xff0c;可以在编译、类加载和运行时被读取&#xff0c;执行相应的处理&#xff0c;简化 Spring的 XML配置。 格式&#xff1a;注解(属性1"属性值1",...) 可以加在类上…...

Spring声明式事务以及事务传播行为

Spring声明式事务以及事务传播行为 Spring声明式事务1.编程式事务2.使用AOP改造编程式事务3.Spring声明式事务 事务传播行为 如果对数据库事务不太熟悉&#xff0c;可以阅读上一篇博客简单回顾一下&#xff1a;MySQL事务以及并发访问隔离级别 Spring声明式事务 事务一般添加到…...

【C语言数据库】Sqlite3基础介绍

1. SQLite简介 SQLite is a C-language library that implements a small, fast, self-contained, high-reliability, full-featured, SQL database engine. SQLite is the most used database engine in the world. SQLite is built into all mobile phones and most computer…...

el-upload上传图片图片、el-load默认图片重新上传、el-upload初始化图片、el-upload编辑时回显图片

问题 我用el-upload上传图片&#xff0c;再上一篇文章已经解决了&#xff0c;el-upload上传图片给SpringBoot后端,但是又发现了新的问题&#xff0c;果然bug是一个个的冒出来的。新的问题是el-upload编辑时回显图片的保存。 问题描述&#xff1a;回显图片需要将默认的 file-lis…...

【拓扑空间】示例及详解1

例1 度量空间的任意两球形邻域的交集是若干球形邻域的并集 Proof&#xff1a; 任取空间的两个球形邻域、&#xff0c;令 任取,令 球形领域 例2 规定X的子集族,证明是X上的一个拓扑 Proof&#xff1a; 1. 2., &#xff08;若干个球形邻域的并集都是的元素&#xff0c;元素…...

linux安装jdk8

上传到某个目录&#xff0c;例如&#xff1a;/usr/local/ tar -xvf jdk-8u144-linux-x64.tar.gz配置环境变量&#xff1a; export JAVA_HOME/usr/local/java export PATH$PATH:$JAVA_HOME/bin设置环境变量&#xff1a; source /etc/profile...

Spring重点知识(个人整理笔记)

目录 1. 为什么要使用 spring&#xff1f; 2. 解释一下什么是 Aop&#xff1f; 3. AOP有哪些实现方式&#xff1f; 4. Spring AOP的实现原理 5. JDK动态代理和CGLIB动态代理的区别&#xff1f; 6. 解释一下什么是 ioc&#xff1f; 7. spring 有哪些主要模块&#xff1f;…...

HTML基础知识详解(上)(如何想知道html的全部基础知识点,那么只看这一篇就足够了!)

前言&#xff1a;在学习前端基础时&#xff0c;必不可少的就是三大件&#xff08;html、css、javascript &#xff09;&#xff0c;而HTML&#xff08;超文本标记语言——HyperText Markup Language&#xff09;是构成 Web 世界的一砖一瓦&#xff0c;它定义了网页内容的含义和…...

如何借助Idea创建多模块的SpringBoot项目

目录 1.1、前言1.2、开发环境1.3、项目多模块结构1.4、新建父工程1.5、创建子模块1.6、编辑父工程的pom.xml文件 1.1、前言 springmvc项目&#xff0c;一般会把项目分成多个包:controler、service、dao、utl等&#xff0c;但是随着项目的复杂性提高&#xff0c;想复用其他一个模…...

爬虫 新闻网站 并存储到CSV文件 以红网为例 V1.0

爬虫&#xff1a;红网网站&#xff0c; 获取当月指定关键词新闻&#xff0c;并存储到CSV文件 V1.0 目标网站&#xff1a;红网 爬取目的&#xff1a;为了获取某一地区更全面的在红网已发布的宣传新闻稿&#xff0c;同时也让自己的工作更便捷 环境&#xff1a;Pycharm2021&#…...

CentOS 使用 Cronie 实现定时任务

CentOS 使用 Cronie 实现定时任务 文章目录 CentOS 使用 Cronie 实现定时任务一、简介二、基本使用1、常用命令2、使用示例第一步&#xff1a;创建脚本/home/create.sh第二步&#xff1a;添加定时任务第三步&#xff1a;重启 cronie 服务额外&#xff1a;查看 cronie 运行状态定…...

java生成word

两种方案 一、poi-tl生成word <dependency><groupId>com.deepoove</groupId><artifactId>poi-tl</artifactId><version>1.12.1</version> </dependency> public static void main(String[] args) throws Exception {String…...

C语言中的结构体:揭秘数据的魔法盒

前言 在C语言的广阔天地中&#xff0c;结构体无疑是一颗璀璨的明珠。它就像是一个魔法盒&#xff0c;能够容纳各种不同类型的数据&#xff0c;并按我们的意愿进行组合和排列。那么&#xff0c;这个魔法盒究竟有何神奇之处呢&#xff1f;让我们一探究竟。 一、结构体的诞生&…...

Listener

文章目录 ListenerServletContextListenerServletContextAttributeListenerHttpSessionListenerHttpSessionAttributeListenerServletRequestListenerServletRequestAttributeListenerHttpSessionBindingListenerHttpSessionActivationListener Listener Listener 监听器它是 J…...

单细胞RNA测序(scRNA-seq)SRA数据下载及fastq-dumq数据拆分

单细胞RNA测序&#xff08;scRNA-seq&#xff09;入门可查看以下文章&#xff1a; 单细胞RNA测序&#xff08;scRNA-seq&#xff09;工作流程入门 单细胞RNA测序&#xff08;scRNA-seq&#xff09;细胞分离与扩增 1. NCBI查询scRNA-seq SRA数据 NCBI地址&#xff1a; https…...

金蝶Apusic应用服务器 未授权目录遍历漏洞复现

0x01 产品简介 金蝶Apusic应用服务器(Apusic Application Server,AAS)是一款标准、安全、高效、集成并具丰富功能的企业级应用服务器软件,全面支持JakartaEE8/9的技术规范,提供满足该规范的Web容器、EJB容器以及WebService容器等,支持Websocket1.1、Servlet4.0、HTTP2.0…...

成都百洲文化传媒有限公司电商服务的新领军者

在当今数字化时代&#xff0c;电商行业正以前所未有的速度蓬勃发展。在这个大背景下&#xff0c;成都百洲文化传媒有限公司凭借其深厚的行业经验和精湛的专业技能&#xff0c;正迅速崛起为电商服务领域的新领军者。 一、专业引领&#xff0c;成就卓越 作为一家专注于电商服务的…...

类似于众人帮的做任务赚佣金网站/引擎优化seo

C语言数组结构行优先顺序存储的实现 (GCC编译)。 1 /**2 * brief C语言 数组 行优先 实现3 * author wid4 * date 2013-11-025 *6 * note 若代码存在 bug 或程序缺陷, 请留言反馈, 谢谢!7 */8 9 #include <stdio.h>10 #include <stdlib.h>11 #include <stdarg.h…...

爱奇艺wordpress/软文案例400字

split -b 1k mis.ini //按大小1k分隔 cat xaa xab>test.ini 将分隔后的文件用cat命令组合成一个新文件...

做网站竞品分析/怎么在百度做宣传广告

data-dismiss"alert"——为关闭button加入该属性能够使其自己主动为警告框赋予关闭功能。 .fade .in——为警告框在关闭时加入动画效果。 很多其它细节參考演示样例&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charse…...

qq空间网站根目录/seo网络推广哪家专业

来源&#xff1a;Forbes&#xff0c;译者&#xff1a;朱焕、闻菲、张冬君&#xff0c; 编译&#xff1a;新智元&#xff08;ID&#xff1a;AI_era&#xff09; 近日《福布斯》刊登对 Facebook CTO Mark Schroepfer 的专访&#xff0c;后者就 Facebook 十年规划与记者深入交谈。…...

网站技术维护/威海网站制作

这是一个功能的示例&#xff1a; 潜在会员可以通过下面的屏幕进行注册。 页面的顶端列出新会员注册的三个步骤&#xff0c;以及当前所处的步骤&#xff1b;在页面的左端是成功交友三步曲&#xff1b;右边是注册帐户表单。 会员输入资料后&#xff0c;单击注册时我们需要进行以下…...

linux wordpress 中毒/推广形式有哪几种

#coding:utf-8二值图像的腐蚀运算 定义&#xff1a;g(x,y) erode[f(x,y),B] AND[Bf(x,y)]其中&#xff0c;g(x,y)为腐蚀后的二值图像&#xff0c;f(x,y)为原始二值图像B为结构元素&#xff0c;Bf(x,y)定义为Bf(x,y) {f(x - bx,y-by),(bx,by)∈B}算子AND(x(i),...,x(n))定义为…...