左神算法题系列：动态规划机器人走路

机器人走路

假设有排成一行的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 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位置，只能向右走 -> cur+1if 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]

假如:
位置数 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

位置/剩余步数	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

代码实现

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]