数据结构与算法-动态规划-机器人达到指定位置方法数
机器人达到指定位置方法数
来自左程云老师书中的一道题
【题目】
假设有排成一行的 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证书的动机与过程 。考证不是主要⽬ 的, 在考证的过程深化⾃⼰的项⽬管理…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
mac:大模型系列测试
0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何,是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试,是可以跑通文章里面的代码。训练速度也是很快的。 注意…...
