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

数据结构与算法-动态规划-机器人达到指定位置方法数

机器人达到指定位置方法数

来自左程云老师书中的一道题

【题目】

假设有排成一行的 N 个位置,记为 1~NN 一定大于或等于 2。开始时机器人在其中的 M

位置上(M 一定是 1~N 中的一个),机器人可以往左走或者往右走,如果机器人来到 1 位置,

那么下一步只能往右来到 2 位置;如果机器人来到 N 位置,那么下一步只能往左来到 N-1 位置。

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

定四个参数 NMKP,返回方法数。

【举例】

N=5,M=2,K=3,P=3

上面的参数代表所有位置为 1 2 3 4 5。机器人最开始在 2 位置上,必须经过 3 步,最后到

达 3 位置。走的方法只有如下 3 种:

1)从 2 到 1,从 1 到 2,从 2 到 3

2)从 2 到 3,从 3 到 2,从 2 到 3

3)从 2 到 3,从 3 到 4,从 4 到 3

所以返回方法数 3。

N=3,M=1,K=3,P=3

上面的参数代表所有位置为 1 2 3。机器人最开始在 1 位置上,必须经过 3 步,最后到达 3

位置。怎么走也不可能,所以返回方法数 0。

递归代码:

public static int process(int N,int M,int K, int P) {if(K == 0) {return M == P? 1:0;}if(M ==1) {return process(N,M+1,K-1,P);}if(M == N) {return process(N,M-1,K-1,P);}return process(N,M+1,K-1,P) + process(N,M-1,K-1,P);}

递归推导动态规划

前提:判断是否是无后效性的。所谓无后效性是指是指一个递归状态的返回值与怎么到达这个状态的路径无关。

  1. 找到什么可变参数可以代表一个递归状态,也就是那些参数一旦确定,返回值也就确定了
  2. 把可变参数的所有组合映射成一张表,有1个可变参数就是一维表,有2个可变参数就是一张二维表….
  3. 最终答案要的是表中哪个位置,在表中标出。
  4. 根据递归的base case ,把这张表最简单、不需要依赖其他位置的那些位置填好
  5. 根据递归过程非base case的部分,也就是分析表中的普遍位置需要怎么计算得到,那么这张表的填写顺序也就确定了
  6. 填好表,返回最终答案在表中位置的值。

动态规划代码:

public static int process2(int N,int M,int K, int P) {int[][] dp = new int[K+1][N+1];dp[0][P] = 1;for(int i =1;i<=K;i++) {for(int j=1;j<=N;j++) {if(j==1) {dp[i][j] = dp[i-1][j+1];} else if(j == N) {dp[i][j] = dp[i-1][j-1];} else {dp[i][j] =  dp[i-1][j+1] + dp[i-1][j-1];}}}return dp[K][M];}

相关文章:

数据结构与算法-动态规划-机器人达到指定位置方法数

机器人达到指定位置方法数 来自左程云老师书中的一道题 【题目】 假设有排成一行的 N 个位置&#xff0c;记为 1~N&#xff0c;N 一定大于或等于 2。开始时机器人在其中的 M 位置上&#xff08;M 一定是 1&#xff5e;N 中的一个&#xff09;&#xff0c;机器人可以往左走或…...

K8S学习指南(2)-docker的基本使用

文章目录 引言安装 DockerDocker 基本概念1. 镜像&#xff08;Images&#xff09;示例&#xff1a;拉取并运行一个 Nginx 镜像 2. 容器&#xff08;Containers&#xff09;示例&#xff1a;查看运行中的容器 3. 仓库&#xff08;Repository&#xff09;示例&#xff1a;推送镜像…...

java 执行linux 命令

文章目录 前言一、linux命令执行二、使用步骤三、踩坑 前言 java 执行linux 命令&#xff1b; 本文模拟复制linux文件到指定文件夹后打zip包后返回zip名称&#xff0c;提供给下载接口下载zip&#xff1b; 一、linux命令执行 linux命令执行Process process Runtime.getRunti…...

ubuntu将本机的wifi网络通过网线分享给另一台机器(用于没有有线网络,重装系统后无wifi驱动或者另一台设备没有wifi网卡)

1.将两台机器通过网线连接 2.在pci ethernet中设置选择另一台机器的mac address&#xff0c;ipv4中选择share to other computer&#xff0c;另一台机器上设置为动态ip&#xff0c;连接上之后另一台机器即可上网。...

Docker + Jenkins + Gitee 自动化部署项目

1.简介 各位看官老爷&#xff0c;本文为Jenkins实战&#xff0c;注重实际过程&#xff0c;阅读完会有以下收获&#xff1a; 了解如何使用Docker安装Jenkins了解如何使用Jenkins部署maven项目了解如何使用JenkinsGitee实现自动化部署 2.Jenkins介绍 相信&#xff0c;正在读这…...

ChatGPT 应用开发(一)ChatGPT OpenAI API 免代理调用方式(通过 Cloudflare 的 AI Gateway)

前言 开发 ChatGPT 应用&#xff0c;我觉得最前置的点就是能使用 ChatGPT API 接口。首先我自己要能成功访问&#xff0c;这没问题&#xff0c;会魔法就可以本地调用。 那用户如何调用到我的应用 API 呢&#xff0c;我的理解是通过用户能访问到的中转服务器向 OpenAI 发起访问…...

【TC3xx】GETH

目录 一、RGMII 二、SMI接口 三、TC3xx MCAL 3.1 MCU 3.2 Port 3.3 DMA 3.4 中断配置 3.5 ETH 3.6 集成 一、RGMII TC3xx支持MII/RMII/RGMII三种以太网数据通信接口。其中RGMII经常用于MAC和MAC之间&#xff0c;或MAC与PHY之间的通信&#xff0c;RGMII的带宽可以是10M…...

不需要联网的ocr项目

地址 GitHub - plantree/ocr-pwa: A simple PWA for OCR, based on Tesseract. 协议 mit 界面 推荐理由 可以离线使用&#xff0c;隐私安全...

【Git使用总结】

Git使用总结 随着软件开发和团队协作的日益重要&#xff0c;Git作为一种强大的版本控制系统&#xff0c;已经成为了开发人员不可或缺的工具。本文将对Git的使用进行总结&#xff0c;以帮助读者更好地掌握Git的用法和技巧。 一、Git的基本概念 在开始使用Git之前&#xff0c;…...

仿照MyBatis手写一个持久层框架学习

首先数据准备&#xff0c;创建MySQL数据库mybatis&#xff0c;创建表并插入数据。 DROP TABLE IF EXISTS user_t; CREATE TABLE user_t ( id INT PRIMARY KEY, username VARCHAR ( 128 ) ); INSERT INTO user_t VALUES(1,Tom); INSERT INTO user_t VALUES(2,Jerry);JDBC API允…...

关东升老师极简系列丛书(由清华大学出版社出版)

极简系列丛书&#xff0c;编程学习新体验 在这个科技日新月异的时代&#xff0c;编程已经成为了一种必备技能。但是面对各种复杂的编程语言&#xff0c;你是否也曾感到过迷茫和困惑&#xff1f;由清华大学出版社出版的“极简系列丛书”就是为了帮助你解决这个问题。 这套丛书…...

要求CHATGPT高质量回答的艺术:提示工程技术的完整指南—第 27 章:如何避开和绕过所有人工智能内容检测器

要求CHATGPT高质量回答的艺术&#xff1a;提示工程技术的完整指南—第 27 章&#xff1a;如何避开和绕过所有人工智能内容检测器 使用高易错性和突发性方法 与人工智能生成的文本相比&#xff0c;人类写作往往具有更多的突发性&#xff0c;这是由于人类往往比人工智能生成的文…...

JavaWeb笔记之MySQL数据库

#Author 流云 #Version 1.0 一、引言 1.1 现有的数据存储方式有哪些&#xff1f; Java程序存储数据&#xff08;变量、对象、数组、集合&#xff09;&#xff0c;数据保存在内存中&#xff0c;属于瞬时状态存储。 文件&#xff08;File&#xff09;存储数据&#xff0c;保存…...

Amazon CodeWhisperer 开箱初体验

文章作者&#xff1a;Coder9527 科技的进步日新月异&#xff0c;正当人工智能发展如火如荼的时候&#xff0c;各大厂商在“解放”码农的道路上不断创造出各种 Coding 利器&#xff0c;今天在下就带大家开箱体验一个 Coding 利器&#xff1a; Amazon CodeWhisperer。 亚马逊云科…...

Java的引用类型有几种?区别是什么?

Java中的引用类型主要分为四种&#xff1a;强引用&#xff08;Strong Reference&#xff09;、软引用&#xff08;Soft Reference&#xff09;、弱引用&#xff08;Weak Reference&#xff09;和虚引用&#xff08;Phantom Reference&#xff09;。这些引用类型在Java中主要用于…...

掌握iText:轻松处理PDF文档-基础篇

关于iText iText是一个强大的PDF处理库&#xff0c;可以用于创建、读取和操作PDF文件。它支持PDF表单、加密和签署等操作&#xff0c;同时支持多种字体和编码。maven的中央仓库中的最新版本是5.X&#xff0c;且iText5不是完全免费的&#xff0c;但是基础能力是免费使用的&…...

小红书民宿文案怎么写?建议收藏

随着民宿市场的日益火爆&#xff0c;如何在众多民宿中脱颖而出&#xff0c;吸引更多租客入住&#xff0c;成为摆在每一位民宿业主面前的难题。一篇优质的小红书民宿文案&#xff0c;不仅能吸引潜在租客的关注&#xff0c;还能提高民宿的知名度。本文伯乐网络传媒将从八个方面教…...

C#教程(一):面向对象

1、介绍 C#是一种多范式编程语言&#xff0c;但其中一个主要的编程范式是面向对象编程&#xff08;OOP&#xff09;。面向对象编程有一些特点&#xff0c;而C#提供了丰富的功能来支持这些特点。 2、面向对象特点 封装&#xff08;Encapsulation&#xff09;&#xff1a; 封装…...

Linux系统中部署minio服务、开启反向代理、二级域名SSL加固

链接: B站1小时-配置指导视频: 一、创建minio 文件目录(/project/minio) 二、下载Minio wget https://dl.min.io/server/minio/release/linux-amd64/minio 三、在minio目录中-创建日志文件 四、对minio(可以理解为windows系统中的.exe可执行文件) 进行授权 chmod 777 min…...

PMP备考总结:项目管理PMP考试提高通过率,轻松上岸~

分享一篇左羊学霸的备考总结&#xff0c;希望能帮到正在备考的友友们~ 前言 作为⼀名通过PMP项⽬管理认证并且拿到3A成绩 ( PMP认证最好成绩) 的 学习者&#xff0c; 来跟⼤家分享下我考取PMP证书的动机与过程 。考证不是主要⽬ 的&#xff0c; 在考证的过程深化⾃⼰的项⽬管理…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

数据分析六部曲?

引言 上一章我们说到了数据分析六部曲&#xff0c;何谓六部曲呢&#xff1f; 其实啊&#xff0c;数据分析没那么难&#xff0c;只要掌握了下面这六个步骤&#xff0c;也就是数据分析六部曲&#xff0c;就算你是个啥都不懂的小白&#xff0c;也能慢慢上手做数据分析啦。 第一…...

RabbitMQ 各类交换机

为什么要用交换机&#xff1f; 交换机用来路由消息。如果直发队列&#xff0c;这个消息就被处理消失了&#xff0c;那别的队列也需要这个消息怎么办&#xff1f;那就要用到交换机 交换机类型 1&#xff0c;fanout&#xff1a;广播 特点 广播所有消息​​&#xff1a;将消息…...