数据结构与算法-动态规划-机器人达到指定位置方法数
机器人达到指定位置方法数
来自左程云老师书中的一道题
【题目】
假设有排成一行的 N 个位置,记为 1~N,N 一定大于或等于 2。开始时机器人在其中的 M
位置上(M 一定是 1~N 中的一个),机器人可以往左走或者往右走,如果机器人来到 1 位置,
那么下一步只能往右来到 2 位置;如果机器人来到 N 位置,那么下一步只能往左来到 N-1 位置。
规定机器人必须走 K 步,最终能来到 P 位置(P 也一定是 1~N 中的一个)的方法有多少种。给
定四个参数 N、M、K、P,返回方法数。
【举例】
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个可变参数就是一张二维表….
- 最终答案要的是表中哪个位置,在表中标出。
- 根据递归的base case ,把这张表最简单、不需要依赖其他位置的那些位置填好
- 根据递归过程非base case的部分,也就是分析表中的普遍位置需要怎么计算得到,那么这张表的填写顺序也就确定了
- 填好表,返回最终答案在表中位置的值。
动态规划代码:
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 个位置,记为 1~N,N 一定大于或等于 2。开始时机器人在其中的 M 位置上(M 一定是 1~N 中的一个),机器人可以往左走或…...
K8S学习指南(2)-docker的基本使用
文章目录 引言安装 DockerDocker 基本概念1. 镜像(Images)示例:拉取并运行一个 Nginx 镜像 2. 容器(Containers)示例:查看运行中的容器 3. 仓库(Repository)示例:推送镜像…...
java 执行linux 命令
文章目录 前言一、linux命令执行二、使用步骤三、踩坑 前言 java 执行linux 命令; 本文模拟复制linux文件到指定文件夹后打zip包后返回zip名称,提供给下载接口下载zip; 一、linux命令执行 linux命令执行Process process Runtime.getRunti…...
ubuntu将本机的wifi网络通过网线分享给另一台机器(用于没有有线网络,重装系统后无wifi驱动或者另一台设备没有wifi网卡)
1.将两台机器通过网线连接 2.在pci ethernet中设置选择另一台机器的mac address,ipv4中选择share to other computer,另一台机器上设置为动态ip,连接上之后另一台机器即可上网。...
Docker + Jenkins + Gitee 自动化部署项目
1.简介 各位看官老爷,本文为Jenkins实战,注重实际过程,阅读完会有以下收获: 了解如何使用Docker安装Jenkins了解如何使用Jenkins部署maven项目了解如何使用JenkinsGitee实现自动化部署 2.Jenkins介绍 相信,正在读这…...
ChatGPT 应用开发(一)ChatGPT OpenAI API 免代理调用方式(通过 Cloudflare 的 AI Gateway)
前言 开发 ChatGPT 应用,我觉得最前置的点就是能使用 ChatGPT API 接口。首先我自己要能成功访问,这没问题,会魔法就可以本地调用。 那用户如何调用到我的应用 API 呢,我的理解是通过用户能访问到的中转服务器向 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之间,或MAC与PHY之间的通信,RGMII的带宽可以是10M…...
不需要联网的ocr项目
地址 GitHub - plantree/ocr-pwa: A simple PWA for OCR, based on Tesseract. 协议 mit 界面 推荐理由 可以离线使用,隐私安全...
【Git使用总结】
Git使用总结 随着软件开发和团队协作的日益重要,Git作为一种强大的版本控制系统,已经成为了开发人员不可或缺的工具。本文将对Git的使用进行总结,以帮助读者更好地掌握Git的用法和技巧。 一、Git的基本概念 在开始使用Git之前,…...
仿照MyBatis手写一个持久层框架学习
首先数据准备,创建MySQL数据库mybatis,创建表并插入数据。 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允…...
关东升老师极简系列丛书(由清华大学出版社出版)
极简系列丛书,编程学习新体验 在这个科技日新月异的时代,编程已经成为了一种必备技能。但是面对各种复杂的编程语言,你是否也曾感到过迷茫和困惑?由清华大学出版社出版的“极简系列丛书”就是为了帮助你解决这个问题。 这套丛书…...
要求CHATGPT高质量回答的艺术:提示工程技术的完整指南—第 27 章:如何避开和绕过所有人工智能内容检测器
要求CHATGPT高质量回答的艺术:提示工程技术的完整指南—第 27 章:如何避开和绕过所有人工智能内容检测器 使用高易错性和突发性方法 与人工智能生成的文本相比,人类写作往往具有更多的突发性,这是由于人类往往比人工智能生成的文…...
JavaWeb笔记之MySQL数据库
#Author 流云 #Version 1.0 一、引言 1.1 现有的数据存储方式有哪些? Java程序存储数据(变量、对象、数组、集合),数据保存在内存中,属于瞬时状态存储。 文件(File)存储数据,保存…...
Amazon CodeWhisperer 开箱初体验
文章作者:Coder9527 科技的进步日新月异,正当人工智能发展如火如荼的时候,各大厂商在“解放”码农的道路上不断创造出各种 Coding 利器,今天在下就带大家开箱体验一个 Coding 利器: Amazon CodeWhisperer。 亚马逊云科…...
Java的引用类型有几种?区别是什么?
Java中的引用类型主要分为四种:强引用(Strong Reference)、软引用(Soft Reference)、弱引用(Weak Reference)和虚引用(Phantom Reference)。这些引用类型在Java中主要用于…...
掌握iText:轻松处理PDF文档-基础篇
关于iText iText是一个强大的PDF处理库,可以用于创建、读取和操作PDF文件。它支持PDF表单、加密和签署等操作,同时支持多种字体和编码。maven的中央仓库中的最新版本是5.X,且iText5不是完全免费的,但是基础能力是免费使用的&…...
小红书民宿文案怎么写?建议收藏
随着民宿市场的日益火爆,如何在众多民宿中脱颖而出,吸引更多租客入住,成为摆在每一位民宿业主面前的难题。一篇优质的小红书民宿文案,不仅能吸引潜在租客的关注,还能提高民宿的知名度。本文伯乐网络传媒将从八个方面教…...
C#教程(一):面向对象
1、介绍 C#是一种多范式编程语言,但其中一个主要的编程范式是面向对象编程(OOP)。面向对象编程有一些特点,而C#提供了丰富的功能来支持这些特点。 2、面向对象特点 封装(Encapsulation): 封装…...
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考试提高通过率,轻松上岸~
分享一篇左羊学霸的备考总结,希望能帮到正在备考的友友们~ 前言 作为⼀名通过PMP项⽬管理认证并且拿到3A成绩 ( PMP认证最好成绩) 的 学习者, 来跟⼤家分享下我考取PMP证书的动机与过程 。考证不是主要⽬ 的, 在考证的过程深化⾃⼰的项⽬管理…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
通过MicroSip配置自己的freeswitch服务器进行调试记录
之前用docker安装的freeswitch的,启动是正常的, 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...
