【力扣】2400. 恰好移动 k 步到达某一位置的方法数目

题目

2400. 恰好移动 k 步到达某一位置的方法数目

在这里插入图片描述

解题思路

在这里插入图片描述

观察上面示例,容易画出下面的递归树,因此可以考虑DFS。

在这里插入图片描述

DFS

很容易写出DFS的代码

class Solution {
    int res = 0;  //记录可行路径数

    public int numberOfWays(int startPos, int endPos, int k) {
        dfs(startPos, endPos, k);
        return res;
    }

    void dfs(int startPos, int endPos, int k){
    	// 递归边界,走了k步
        if(k == 0){
        	// 走到终点了,答案加一
            if(startPos == endPos){
                res++;
            }
            return;
        }
        // 向左走
        dfs(startPos - 1, endPos, k - 1);
        // 向右走
        dfs(startPos + 1, endPos, k - 1);
    }
}

记忆化搜索

上述代码可以解决示例1,对于规模大一点的例子就超时,说明思路是对的,接下来就是优化了,自然的想法就是加个备忘录,那就要考虑是否存在重叠子问题。

对于示例1,下图展示了存在的重叠子问题。

在这里插入图片描述
在上图中,当前的坐标和剩余 k 步就是问题的状态,因此加一个二维数组备忘录 memo。

注意:由于坐标可能是负值,所以可以用 startPos + 偏移 来防止数组索引为负值。

class Solution {
	// 备忘录
    int[][] memo;
    // 取余
    int MOD = 1000000000 + 7;

    public int numberOfWays(int startPos, int endPos, int k) {
    	// 初始化备忘录
        memo = new int[6000 + 10][6000 + 10];
        for(int[] arr : memo){
            Arrays.fill(arr, -1);
        }
        return dfs(startPos, endPos, k);
    }

    int dfs(int startPos, int endPos, int k){
    	// 已经计算过该子问题,则直接返回
        if(memo[startPos + 3000][k] != -1){
            return memo[startPos + 3000][k];
        }
        // 走完 k 步
        if(k == 0){
            if(startPos == endPos){  // 走到终点了,是一种方法
                memo[startPos + 3000][k] = 1;
            }else{  // 没有走到终点,方案数为0
                memo[startPos + 3000][k] = 0;
            }
            return memo[startPos + 3000][k];
        }
        // 记录往左走和往右走的方案总数
        int res = 0;
        // 加上往左走的方案数
        res += dfs(startPos - 1, endPos, k - 1);
        // 加上往右走的方案数
        res += dfs(startPos + 1, endPos, k - 1);
        // 结果求余
        memo[startPos + 3000][k] = res % MOD;
        return memo[startPos + 3000][k];
    }
}
本文转载于网络 如有侵权请联系删除

相关文章

  • EasyNTS上云网关网络穿透/远程运维在系统维护中的应用

    随着互联网的兴起,计算机安全问题也日益得到重视,对外维护的端口需要通过4A或堡垒机实现。如若使用堡垒机,用户主机侧需要能打开堡垒机的页面,堡垒机侧到设备端的端口要畅通。因此很多情况下通过4A和堡垒机,过程繁琐且操作维护很不方便。对此我们有了新的考虑,如何在保证计算机系统安全的前提下,简化端口的运维呢?对此EasyNTS上云网关系统似乎可以解决这一问题。大家知道EasyNTS是软硬一体的设备,大家也许知道比较多的是视频拉转推功能,但其实EasyNTS在研发之初的功能是网络穿透和远程运维。可以使用EasyNTS上云网关系统实现端口统一管理,既可以减少端口暴露带来的风险,还方便维护。只需要在网络有一台服务器,带有固定IP,部署我们的EasyNTS系统,将所有的设备通过防火墙策略把远程的地址限制到EasyNTS所在的服务器中。在EasyNTS上将对应服务器的端口穿透出来,方便了研发的日常维护,大大提高了工作效率。端口使用后,可以及时关闭穿透后的端口,避免端口暴露。EasyNTS上云网关硬件置于设备现场,管理平台运行于阿里云/腾讯云等,做到随时随地管控所有现场的设备,极大地降低了现场的运维成本。

  • 2.Model设计

    Model设计1.在settings.py中配置:AUTH_USER_MODEL='users.UserProfile'复制2.在apps/users/models.py中:fromdjango.dbimportmodels fromdjango.contrib.auth.modelsimportAbstractUser fromdatetimeimportdatetime fromdjango.utils.safestringimportmark_safe #Createyourmodelshere. classUserProfile(AbstractUser): """ 用户表 """ token=models.CharField(max_length=64,null=True,blank=True,verbose_name='token') name=models.CharField(max_length=10,null=True,blank=True,verbose_name

  • Python爬小草1024图片,盖达尔的

    项目说明:Python版本:3.7.2模块:urllib.request,re,os,ssl目标地址:http://小草.com/第二个爬虫项目,设备转移到了Mac上,Mac上的Pycharm有坑, 环境变量必须要配置好,解释器要选对,不然模块加载不出来 项目实现: #!/usr/bin/envpython3 #-*-coding:utf-8-*- #__author__='vic' ##导入模块 importurllib.request,re,os复制小草图片下载有ssl证书验证,我们全局跳过验证ssl._create_default_https_context=ssl._create_unverified_context复制一、设置代理小草服务器在海外,需要绕过GFW,代理软件选择的是ssX-NG,偏好设置查看监听地址 Path='/Users/vic/Pictures/' ##设置代理,http和https都用的是http监听,也可以改为sock5 proxy=urllib.request.ProxyHandler({'http&

  • MVC Html.DropDownList 和DropDownListFor 的常用方法

    一、非强类型:Controller:ViewData["AreId"]=fromainrp.GetArea() selectnewSelectListItem{ Text=a.AreaName, Value=a.AreaId.ToString() }; View: @Html.DropDownList("AreId")复制 还可以给其加上一个默认选项:@Html.DropDownList("AreId","请选择");二、强类型:DropDownListFor常用的是两个参数的重载,第一参数是生成的select的名称(属性)【给属性绑定值】,第二个参数是数据,用于将绑定数据源至DropDownListForModle:publicclassSettingsViewModel { Repositoryrp=newRepository(); publicstringListName{get;set;} publicIEnumerable<SelectListItem>GetSelectList()

  • PM2 node进程管理工具 自动部署小结

    PM2的功能不多做介绍了,总之使用简单,功能强大。 今天实现了本地自动部署node项目到服务器的流程。简单总结下几个注意点。 建议先看文档先要保证要部署的服务器上(以下简称server)能直接ssh拉仓库代码,比如gitclonegit@gitee.com:finley/demo.git。不行的话配下server生成ssh-key,然后把publickey告诉代码仓库服务商,比如coding.net,github。权限问题,比如server的登录用户是Ubuntu,将来项目要部署在/home/ubuntu下面,可以执行下sudochownubuntu:ubuntu/home/ubuntu/.pm2/*不然可能会部署失败。部署成功后会在配置的项目路径里出现以下三个目录:current--当前服务运行的文件夹(是source的软链接) share--logpid等共享数据 source--clone下来的源代码 配置脚本module.exports={ /** *Applicationconfigurationsection *http://pm2.keymetrics.io/docs/u

  • PHP新手必须认识的一些建议

    这些建议都是我自身亲历成长过程中积累的一些看法,仅作参考,相信百分之八十对你都有帮助!刚学习PHP的时候不要纠结使用哪个环境?appserv、wamp集成环境都不错编辑器很多种,但最好熟悉其中一种,养成手写代码习惯常用的函数要熟记环境报错全开启,把NOTICE屏蔽遇到报错要仔细看报错原因,行号,分析解决方法POST与GET的区别SESSION与COOKIE的区别不要使用COOKIE记录重要信息,如密码不要在数据库中明文存储密码传输中文一定要URLENCODE,JS异步提交同样Ajax响应页面最好使用JSON,特别是有中文或者特殊符号时知道require与include区别项目部署时相关配置信息文件不要在WEB根目录下使用文件夹分层存储上传文件,不要全部上传文件都放在upload一个文件夹下上传文件只能使用POST,FORM表单要声明enctype=”multipart/form-data”思考验证码的验证机制,实现方式MC如何配合PHP做cache思考如何使用PHP生成HTML静态页永远不要相信用户输入的信息思考for($i=0;$i<count($array);$i++){..

  • 数据结构-二叉树遍历总结

    二叉树结构二叉树是一种特殊的树,每个父结点最多只能用有两个子结点。 在树中,按照结点的“继承”关系可以分为父结点和子结点; 按照结点的位置关系可以分为根结点,中间结点和叶结点。 其中叶结点没有子结点。 我们用结点中的数字代表结点,那么在上图中:10为根结点;6、14为中间结点;4、8、12、16为叶节点。二叉树存储结构二叉树结构可以使用链式和顺序两种方式实现,其中比较常用的链式存储结构:链式结构typedefcharTElemType; typedefstructBiTNode/*结点结构*/ { TElemTypedata;/*结点数据*/ structBiTNode*lchild,*rchild;/*左右孩子指针*/ }BiTNode,*BiTree;复制也可以写成这样,更清晰一些:typedefcharTElemType; typedefstructBiTNode{ TElemTypedata; structBiTNode*lchild; structBiTNode*rchild; }BiTNode; typedefBiTNode*BiTree;复制顺序结构#defineLEN

  • ASP.NET Core 6.0 基于模型验证的数据验证

    1前言 在程序中,需要进行数据验证的场景经常存在,且数据验证是有必要的。前端进行数据验证,主要是为了减少服务器请求压力,和提高用户体验;后端进行数据验证,主要是为了保证数据的正确性,保证系统的健壮性。 本文描述的数据验证方案,是基于官方的模型验证(Modelvalidation),自定义其返回格式的方案。是笔者近期面试过程中才得知的方式【之前个人混淆了:模型验证(Modelvalidation)和EF模型配置的数据注释(Dataannotation)方式】。 注:MVC和API的模型验证有些许差异,本文主要描述的是API下的模型验证。 1.1数据验证的场景 比较传统的验证方式如下: publicstringTraditionValidation(TestModelmodel) { if(string.IsNullOrEmpty(model.Name)) { return"名字不能为空!"; } if(model.Name.Length>10) { return"名字长度不能超过10!"; } return"验证通过!"; } 复制 在函数中,对模型的各个属性分别做验证。 虽然函

  • SQL Server使用索引实现数据访问优化

    一、简介 自从你和你的团队成功的开发和部署了一个INTERNET网站,已经过去数月了,这个网站在很短的时间内吸引了数千用户前来注册和使用,因此你有了一个非常满意的客户。包括你和你的团队、管理层、客户,每个人都非常高兴。 生活并不总是一帆风顺的。当站点的用户开始日均高速增长的时候,问题随即出现了,客户发来邮件开始抱怨网站性能太慢,同时称网站正在丢失客户。 你开始调查这个系统,很快你发现当系统访问或更新数据的时候,速度非常慢。打开数据库一看,数据库的记录增加的很快,有些表的记录达到了成千上万行,测试团队在产品数据库上做了一个测试,结果发现在测试服务器上仅2/3秒就能完成的一个处理过程,现在需要5分钟。” 这个古老的故事发生在全球范围内的数以千计的系统身上。包括我在内,几乎每个开发人员在他或她的开发过程中会碰到同样的事情。我知道为什么这样的情形会发生,同时我也知道如何去克服它。 二、阅读范围 请注意本一系列文章讨论的主要的焦点是“事务性的SQLServer数据库数据访问性能优化”,但大部分优化技术同样适用于其他的数据库。 我将要讨论的优化技术仅仅适用于软件开发人员。作为一个开发者,你需要跟随

  • 2019-2020-2 20175212童皓桢《网络对抗技术》 Exp1 PC平台逆向破解

    2019-2020-220175212童皓桢《网络对抗技术》 Exp1PC平台逆向破解 目录 1.实验目标 2.实验内容 2.1直接修改程序机器指令,改变程序执行流程 2.2通过构造输入参数,造成BOF攻击,改变程序执行流 2.3注入Shellcode并执行 3、答老师问 3.1实验收获与感想 3.2什么是漏洞?漏洞有什么危害? 4、遇到的问题及其解决方法 5、参考资料 1.实验目标 实验一的实践对象是一个名为pwn1的linux可执行文件。 该程序正常执行流程是:main调用foo函数,foo函数会简单回显任何用户输入的字符串。 实验目标为:使程序执行另一个代码片段getshell 本实验的三个实践内容为: 1、手工修改可执行文件,改变程序执行流程,直接跳转到getShell函数。 2、利用foo函数的Bof漏洞,构造一个攻击输入字符串,覆盖返回地址,触发getShell函数。 3、注入一个自己制作的shellcode并运行这段shellcode。 分别对应现实攻击中的: 1.运行原本不可访问的代码片段 2.强行修改程序执行流 3.注入运行任意

  • sql如何去除重复的数据-好点的

    sql如何去除重复的数据-好点的 之前写的mysql去重多个字段,是不太对的。因为我是用distinct(xm,phone)去重,然后将xm,phone为唯一的数据插入新表,但是数据中有三个字段:id,xm,phone,我上一种方法是没法插入id的,因为xm,phone重复的加上id,就变成不重复的了。 例子: idnamphone1张三1232张三123这本来是重复的数据,但是如果distinc*就成了两条不重复的数据了,因为前面的id不重复复制 INSERTintochongfubiao_quchong_copy(id,nam,phone)selectdistinct* fromchongfubiao_quchong;复制 而下面这种又会有语法错误[Err]ERROR:INSERThasmoretargetcolumnsthanexpressions;因为查询的是两栏插入的是三栏 INSERTintochongfubiao_quchong_copy1(id,nam,phone)selectdistinctnam,phone fromchongfubiao_quc

  • 有用的iOS网站地址

    王巍(@onevcat)是一名iOS和Unity3D开发者,现旅居日本,正在寻求创意之源。http://swifter.tips/http://onevcat.com/2013/02/xcode-plugin/ http://blog.devtang.com/唐巧的技术博客 https://ios-development.zeef.com/dcode.tapeihttps://ios-9.zeef.com/robin.eggenkamphttps://swift.zeef.com/robin.eggenkamp   郭曜源http://blog.ibireme.com/(Garannodou) 不会开机的男孩http://studentdeng.github.io/   有用的java地址http://cmsblogs.com/?p=1574   Spark(jdk1.8) http://sparkjava.com/documentation https://github.com/perwendel/spark#examples   Angula

  • 数组的length属性不是只读的,你知道吗?

    数组的length属性不是只读的 varcolor=['red','blue','green']; color.length=2; console.log(color); //["red","blue"]复制  

  • 小甲鱼Python第033讲:异常处理:你不可能总是对的2| 课后测试题及参考答案

    测试题: 0.我们使用什么方法来处理程序中出现的异常?   使用try......except搭配来捕获处理程序中的出现的异常。 try: 检测范围 exceptException[asreason]: 出现异常(Exception)后的处理代码复制   1.一个try语句可以和多个except语句搭配吗?为什么?   可以。因为try语句块中可能出现多类异常,利用多个except语句可以分别捕获并处理我们感兴趣的异常。 1try: 2sum=1+'1' 3f=open('我是一个不存在的文档.txt') 4print(f.read) 5f.close() 6exceptOSErrorasreason: 7print("文件出错了\n错误原因是:"+str(reason)) 8exceptTypeErrorasreason: 9print("类型出错了\n错误原因是:"+str(reason))复制   2.你知道如何统一处理多类异常吗?   在except后边使用小括号()把多个需要统一处理的异常括起来: 1try: 2int("abc") 3sum=1

  • 查询方圆30km的东西

      //按经纬度查询附近机场 //$point=$address['content']['point']; //$Lnt=$point['x']; //$Lat=$point['y']; //$distance=30;//范围(单位千米) //define('EARTH_RADIUS',6371);//地球半径,平均半径为6371km //$dlnt=2*asin(sin($distance/(2*EARTH_RADIUS))/cos(deg2rad($Lat))); //$dlnt=rad2deg($dlnt); //$dlat=$distance/EARTH_RADIUS; //$dlat=rad2deg($dlat); //$squares=array( //'left-top'=>array('lat'=>$Lat+$dlat,'lnt'=>$Lnt-$dlnt), //'right-top'=>array('lat'=>$Lat+$dlat,'lnt'=>$Lnt+$dlnt), //'left-bottom'=>arr

  • 从线段树的可删减性谈树状数组

    这可能是我最后一次更新博客了呢 #前言 很久之前,我初学树状数组的时候感觉非常的复杂、神奇、晦涩难懂。。。 果然还是我太菜了。后来了解到线段树的可删减性,这两者就自然而然的联系在一起了。   #线段树的可删减性 很显然,对于一些区间操作的问题,线段树有着绝对的优势,基本上只要是区间查询之类的问题,那线段树是没跑了。 但是如果我们要查询的是前缀和这样的东西的话,会不会感觉线段树中的一些东西是多余的呢? 这么说可能有些不好理解,画画图就好: 上图如果看不清楚,请在新标签页中打开。(蓝色为节点标号,红色是区间端点) 假设我们查询到位置9的前缀和,那么答案就等于2号节点和6号节点的和。 这两个节点有什么奇怪的性质? 显然它们都是左孩子啊,那是不是所有的前缀和都是仅由左孩子节点构成的呢。 再试一下,就会发现,都是这样的。如何证明? 从根节点开始,答案有以下两种情况。 在左孩子中。 整个左孩子就是答案。 整个左孩子加上右孩子的一部分。 先看第二种情况。。。那这根本没有悬念吧,只有左孩子。 那再看第一种情况,在左孩子中查找答案。那么答案还是分成上面的三种情况。 关键的就是来看第三种情

  • 更好的理解 php 浮点类型

    更好的理解php浮点类型 目录更好的理解php浮点类型例子实验precision思考 例子 先来个简单的例子,这个例子很多人喜欢,而且也最能说明问题。 $a=0.58*100; var(intval($a)); 复制 输出结果是57,相信很多人也看过这类的说明,也有很多文章说不要相信浮点运算,任何语言都是。 接着我们来看看到底是怎么回事,其实在0.58*100时计算机内部二进制存储时是有误差的,只不过显示不出来而已。 实验 那我们再做个实验。 $a=57.9999999999999; echo$a; 复制 上面显示的是58,所以对于浮点类型的值,眼见不一定为实。 precision 经过群里小伙伴的提醒,PHP设置中有一个precision配置,用于显示浮点有效位数的。 当设置为-1时就可以显示出原始数据,那时候就眼见为实了。 但是如果使用-1的配置,在使用BCMath库的相关函数时会过于精度无法正确判断,比如,当precision为-1时,bccomp(0.58*100,58,2)返回是-1,当precision为默认14时返回为0。 思考 以下结果是什么? $a=57.99999

  • BZOJ 4004 [JLOI2015]装备购买 | 线性基

    题目链接 LuoguP3265 题解 非常正常的线性基! 但是我不会线性基…… (吐槽:#definedoublelongdouble才过……) #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> #definespaceputchar('') #defineenterputchar('\n') typedeflonglongll; usingnamespacestd; template<classT> voidread(T&x){ charc; boolop=0; while(c=getchar(),c<'0'||c>'9') if(c=='-')op=1; x=c-'0'; while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0'; if(op)x=-x; } template<classT&

  • foreach ($users as $key=&gt;$value)

    1:foreach(array_nameas$value){statement;}这里的array_name是你要遍历的数组名,每次循环中,array_name数组的当前元素的值被赋给$value,并且数组内部的下标向下移一步,也就是下次循环回得到下一个元素。2:foreach(array_nameas$key=>$value){statement;}这里跟第一种方法的区别就是多了个$key,也就是除了把当前元素的值赋给$value外,当前元素的键值也会在每次循环中被赋给变量$key。键值可以是下标值,也可以是字符串。比如book[0]=1中的“0”,book[id]="001"中的“id”.复制 自信与努力用心坚持

  • linux 文件内容乱码 文件内容转码

    1、使用明细 iconv文件内容转码 iconv-fGB2312-tUTF-8机构合并.csv>jghb.csv 复制 2、源文件编码查看 file filename 自动化学习。

  • 11.16 站立会议第二天

    时间:晚八点 地点:三栋 昨天确立了思路,今天编写了部分登陆程序界面的代码,制作了索引卡并打印分发给小组成员,明天将查阅各种格式类型,打算插入进代码中,适情况将相同文件的判断解决。

相关推荐

推荐阅读