机器人走路
假设有排成一行的N个位置记为1~N,N一定大于或等于2
开始时机器人在其中的start位置上(start一定是1~N中的一个)
如果机器人来到1位置,那么下一步只能往右来到2位置;
如果机器人来到N位置,那么下一步只能往左来到N-1位置;
如果机器人来到中间位置,那么下一步可以往左走或者往右走;
规定机器人必须走K步,最终能来到aim位置(P也是1~N中的一个)的方法有多少种
给定四个参数 N,start,aim,K 返回能走到的方法数
递归思路
1、当cur在1位置时,只能向2位置移动
2、当cur在N位置时,只能向N-1位置移动
3、当cur在中间位置,可以向cur+1位置移动、也可以向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 0
return 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的方法数
"""
# 步数走完时,如果机器人刚好到达目标位置,则返回1
if rest == 0:
return 1 if cur == target else 0
# 如果在1位置,只能向右走 -> cur+1
if cur == 1:
return self.process_a(pos, cur + 1, rest - 1, target)
# 如果在最后一个位置,只能向左 -> cur-1
if 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:
# 步数走完时,如果机器人刚好到达目标位置,则返回1
if rest == 0:
index = 1 if cur == target else 0
elif 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] = index
return cache[cur][rest]
假如:
位置数 pos=6
剩余步数steps=5
开始位置start=1
目标位置target=4
cur为当前位置
创建动态表dp 行代表位置数 pos(1,pos), 列代表剩余步数rest(0,steps)
根据递归条件填表:
1、当剩余步数为0时,刚好来到target位置,dp值为1,如果在其他位置,说明未到目标位置,dp值为0
即:dp[cur][rest] = dp[4][0] = 1
2、当cur=1时,只能向2位置移动,都依赖dp[2][rest-1]位置的值
3、当cur=pos时,只能向pos-1位置移动,都依赖dp[pos-1][rest-1]位置的值
4、当1<cur<pos时,既能向cur-1位置移动,也能向cur+1位置移动,都依赖dp[cur-1][rest-1]+dp[cur+1][rest-1]
最终求dp[start][rest] --> dp[1][5] = 4
| cur/rest文章来源:https://www.toymoban.com/news/detail-735133.html
位置/剩余步数 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | x | x | x | x | x | x |
1 | 0 | 0 | 0 | 1 | 0 | 4 |
2 | 0 | 0 | 1 | 0 | 4 | 0 |
3 | 0 | 1 | 0 | 3 | 0 | 10 |
4 | 1 | 0 | 2 | 0 | 6 | 0 |
5 | 0 | 1 | 0 | 3 | 0 | 9 |
6 | 0 | 0 | 1 | 0 | 3 | 0 |
代码实现文章来源地址https://www.toymoban.com/news/detail-735133.html
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, 其他位置值为0
dp[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]
到了这里,关于左神算法题系列:动态规划机器人走路的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!