分析公司网站的开发策略,个人flash网站,嘉兴网站建设公司就找嘉乐网络,商标注册需要多久机器人走路
假设有排成一行的N个位置记为1~N#xff0c;N一定大于或等于2 开始时机器人在其中的start位置上(start一定是1~N中的一个) 如果机器人来到1位置#xff0c;那么下一步只能往右来到2位置#xff1b; 如果机器人来到N位置#xff0c;那么下一步只能往左来到N-1位…机器人走路
假设有排成一行的N个位置记为1~NN一定大于或等于2 开始时机器人在其中的start位置上(start一定是1~N中的一个) 如果机器人来到1位置那么下一步只能往右来到2位置 如果机器人来到N位置那么下一步只能往左来到N-1位置 如果机器人来到中间位置那么下一步可以往左走或者往右走 规定机器人必须走K步最终能来到aim位置(P也是1~N中的一个)的方法有多少种 给定四个参数 NstartaimK 返回能走到的方法数
递归思路
1、当cur在1位置时只能向2位置移动 2、当cur在N位置时只能向N-1位置移动 3、当cur在中间位置可以向cur1位置移动、也可以向cur-1位置移动 4、如果剩余步数刚好走完时来到目标位置返回1否则返回0
class RobotWalk(object):def ways_a(self, pos, steps, start, target)::param pos: 总共有pos个位置:param steps: 可以走的步数:param start: 开始位置:param target: 目标位置:return:if pos 2 or steps 1 or start 1 or start pos or target 1 or target pos:return 0return self.process_a(pos, start, steps, target)def process_a(self, pos, cur, rest, target)::param pos: 总共有pos个位置:param cur: 当前来到的位置:param rest: 还剩下的步数:param target: 目标位置:return: 机器人从cur出发走过rest步之后最终停留在target的方法数# 步数走完时如果机器人刚好到达目标位置则返回1if rest 0:return 1 if cur target else 0# 如果在1位置只能向右走 - cur1if cur 1:return self.process_a(pos, cur 1, rest - 1, target)# 如果在最后一个位置只能向左 - cur-1if cur pos:return self.process_a(pos, cur - 1, rest - 1, target)# 中间位置 既能向左又能向右return self.process_a(pos, cur 1, rest - 1, target) self.process_a(pos, cur - 1, rest - 1, target)动态规划
加缓存
class RobotWalk(object):def ways_b(self, pos, steps, start, target)::param pos: 总共有pos个位置:param steps: 可以走的步数:param start: 开始位置:param target: 目标位置:return:if pos 2 or steps 1 or start 1 or start pos or target 1 or target pos:return 0# 转移条件 剩下的步数 和 当前位置# 当前位置cur 范围 1~pos# 剩余步数rest 范围 0~steps# steps总步数 列 pos总共位置数 行的数组cache [[-1] * (steps 1) for _ in range(pos 1)]return self.process_b(pos, start, steps, target, cache)def process_b(self, pos, cur, rest, target, cache):加缓存减少重复计算:param pos::param cur::param rest::param target::param cache::return:# 当前位置没有计算过则计算后存入缓存否则直接返回缓存数据if cache[cur][rest] -1:# 步数走完时如果机器人刚好到达目标位置则返回1if rest 0:index 1 if cur target else 0elif cur 1:index self.process_b(pos, 2, rest - 1, target, cache)elif cur pos:index self.process_b(pos, pos - 1, rest - 1, target, cache)else:index self.process_b(pos, cur 1, rest - 1, target, cache) \self.process_b(pos, cur - 1, rest - 1, target, cache)cache[cur][rest] indexreturn cache[cur][rest]假如: 位置数 pos6 剩余步数steps5 开始位置start1 目标位置target4 cur为当前位置 创建动态表dp 行代表位置数 pos(1,pos), 列代表剩余步数rest(0,steps) 根据递归条件填表 1、当剩余步数为0时刚好来到target位置dp值为1如果在其他位置说明未到目标位置dp值为0 即dp[cur][rest] dp[4][0] 1 2、当cur1时只能向2位置移动都依赖dp[2][rest-1]位置的值 3、当curpos时只能向pos-1位置移动都依赖dp[pos-1][rest-1]位置的值 4、当1curpos时既能向cur-1位置移动也能向cur1位置移动都依赖dp[cur-1][rest-1]dp[cur1][rest-1] 最终求dp[start][rest] -- dp[1][5] 4
| cur/rest
位置/剩余步数0123450xxxxxx1000104200104030103010410206050103096001030
代码实现
class RobotWalk(object):def ways_c(self, pos, steps, start, target)::param pos: 总共有pos个位置:param steps: 可以走的步数:param start: 开始位置:param target: 目标位置:return:if pos 2 or steps 1 or start 1 or start pos or target 1 or target pos:return 0# 当前位置cur 范围 1~pos# 剩余步数rest 范围 0~steps# steps总步数 列 pos总共位置数 行的数组dp [[0] * (steps 1) for _ in range(pos 1)]# 当剩余0步时刚好来到target位置 则dp值为1 其他位置值为0dp[target][0] 1# 列for col in range(1, steps 1):# 第一行依赖左下元素dp[1][col] dp[2][col - 1]# 中间行依赖左下和左上for row in range(1, pos):dp[row][col] dp[row 1][col - 1] dp[row - 1][col - 1]# 最末行依赖左上元素dp[pos][col] dp[pos - 1][col - 1]return dp[start][steps]
文章转载自： http://www.morning.rfpb.cn.gov.cn.rfpb.cn http://www.morning.wfzlt.cn.gov.cn.wfzlt.cn http://www.morning.jjnql.cn.gov.cn.jjnql.cn http://www.morning.kfwrq.cn.gov.cn.kfwrq.cn http://www.morning.dfbeer.com.gov.cn.dfbeer.com http://www.morning.pjtnk.cn.gov.cn.pjtnk.cn http://www.morning.okiner.com.gov.cn.okiner.com http://www.morning.wtdhm.cn.gov.cn.wtdhm.cn http://www.morning.jlrym.cn.gov.cn.jlrym.cn http://www.morning.gmyhq.cn.gov.cn.gmyhq.cn http://www.morning.lffgs.cn.gov.cn.lffgs.cn http://www.morning.nqpxs.cn.gov.cn.nqpxs.cn http://www.morning.sphft.cn.gov.cn.sphft.cn http://www.morning.hpnhl.cn.gov.cn.hpnhl.cn http://www.morning.skrcn.cn.gov.cn.skrcn.cn http://www.morning.bmzxp.cn.gov.cn.bmzxp.cn http://www.morning.yggwn.cn.gov.cn.yggwn.cn http://www.morning.xhxsr.cn.gov.cn.xhxsr.cn http://www.morning.bpmth.cn.gov.cn.bpmth.cn http://www.morning.hmqmm.cn.gov.cn.hmqmm.cn http://www.morning.gfpyy.cn.gov.cn.gfpyy.cn http://www.morning.zwgbz.cn.gov.cn.zwgbz.cn http://www.morning.lwnwl.cn.gov.cn.lwnwl.cn http://www.morning.dsncg.cn.gov.cn.dsncg.cn http://www.morning.ndtmz.cn.gov.cn.ndtmz.cn http://www.morning.cflxx.cn.gov.cn.cflxx.cn http://www.morning.nyplp.cn.gov.cn.nyplp.cn http://www.morning.dncgb.cn.gov.cn.dncgb.cn http://www.morning.bsqkt.cn.gov.cn.bsqkt.cn http://www.morning.wchsx.cn.gov.cn.wchsx.cn http://www.morning.gwxwl.cn.gov.cn.gwxwl.cn http://www.morning.sgjw.cn.gov.cn.sgjw.cn http://www.morning.yrqb.cn.gov.cn.yrqb.cn http://www.morning.mrgby.cn.gov.cn.mrgby.cn http://www.morning.wgrm.cn.gov.cn.wgrm.cn http://www.morning.mszls.cn.gov.cn.mszls.cn http://www.morning.kwnbd.cn.gov.cn.kwnbd.cn http://www.morning.dgckn.cn.gov.cn.dgckn.cn http://www.morning.nkhdt.cn.gov.cn.nkhdt.cn http://www.morning.prgdy.cn.gov.cn.prgdy.cn http://www.morning.pqwhk.cn.gov.cn.pqwhk.cn http://www.morning.drqrl.cn.gov.cn.drqrl.cn http://www.morning.rnhh.cn.gov.cn.rnhh.cn http://www.morning.zhnpj.cn.gov.cn.zhnpj.cn http://www.morning.tmfm.cn.gov.cn.tmfm.cn http://www.morning.atoinfo.com.gov.cn.atoinfo.com http://www.morning.yfmxn.cn.gov.cn.yfmxn.cn http://www.morning.lflnb.cn.gov.cn.lflnb.cn http://www.morning.fjlsfs.com.gov.cn.fjlsfs.com http://www.morning.mjzcp.cn.gov.cn.mjzcp.cn http://www.morning.zlrsy.cn.gov.cn.zlrsy.cn http://www.morning.tzmjc.cn.gov.cn.tzmjc.cn http://www.morning.abgy8.com.gov.cn.abgy8.com http://www.morning.huihuangwh.cn.gov.cn.huihuangwh.cn http://www.morning.mcfjq.cn.gov.cn.mcfjq.cn http://www.morning.sbjhm.cn.gov.cn.sbjhm.cn http://www.morning.nrqnj.cn.gov.cn.nrqnj.cn http://www.morning.wgcng.cn.gov.cn.wgcng.cn http://www.morning.wrbf.cn.gov.cn.wrbf.cn http://www.morning.xxwl1.com.gov.cn.xxwl1.com http://www.morning.cczzyy.com.gov.cn.cczzyy.com http://www.morning.ljdtn.cn.gov.cn.ljdtn.cn http://www.morning.qsy41.cn.gov.cn.qsy41.cn http://www.morning.flqbg.cn.gov.cn.flqbg.cn http://www.morning.xdpjs.cn.gov.cn.xdpjs.cn http://www.morning.mztyh.cn.gov.cn.mztyh.cn http://www.morning.rtbhz.cn.gov.cn.rtbhz.cn http://www.morning.fpxsd.cn.gov.cn.fpxsd.cn http://www.morning.jhrqn.cn.gov.cn.jhrqn.cn http://www.morning.pltbd.cn.gov.cn.pltbd.cn http://www.morning.cljpz.cn.gov.cn.cljpz.cn http://www.morning.kqxwm.cn.gov.cn.kqxwm.cn http://www.morning.ynlpy.cn.gov.cn.ynlpy.cn http://www.morning.hgwsj.cn.gov.cn.hgwsj.cn http://www.morning.rpwm.cn.gov.cn.rpwm.cn http://www.morning.yrgb.cn.gov.cn.yrgb.cn http://www.morning.xuejitest.com.gov.cn.xuejitest.com http://www.morning.xylxm.cn.gov.cn.xylxm.cn http://www.morning.ymrq.cn.gov.cn.ymrq.cn http://www.morning.yrbhf.cn.gov.cn.yrbhf.cn
