機器人走路

假設有排成一行的N個位置記為1~N，N一定大于或等于2
開始時機器人在其中的start位置上(start一定是1~N中的一個)
如果機器人來到1位置，那么下一步只能往右來到2位置；
如果機器人來到N位置，那么下一步只能往左來到N-1位置；
如果機器人來到中間位置，那么下一步可以往左走或者往右走；
規(guī)定機器人必須走K步，最終能來到aim位置(P也是1~N中的一個)的方法有多少種
給定四個參數(shù) N，start，aim，K 返回能走到的方法數(shù)

遞歸思路

1、當cur在1位置時，只能向2位置移動
2、當cur在N位置時，只能向N-1位置移動
3、當cur在中間位置，可以向cur+1位置移動、也可以向cur-1位置移動
4、如果剩余步數(shù)剛好走完時，來到目標位置，返回1，否則返回0

class RobotWalk(object):def ways_a(self, pos, steps, start, target):""":param pos: 總共有pos個位置:param steps: 可以走的步數(shù):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: 還剩下的步數(shù):param target: 目標位置:return: 機器人從cur出發(fā)，走過rest步之后，最終停留在target的方法數(shù)"""# 步數(shù)走完時，如果機器人剛好到達目標位置，則返回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)

動態(tài)規(guī)劃

加緩存

class RobotWalk(object):def ways_b(self, pos, steps, start, target):""":param pos: 總共有pos個位置:param steps: 可以走的步數(shù):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# 轉移條件 剩下的步數(shù) 和 當前位置# 當前位置cur 范圍 1~pos# 剩余步數(shù)rest 范圍 0~steps# steps（總步數(shù)） 列 pos（總共位置數(shù)） 行的數(shù)組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:"""# 當前位置沒有計算過，則計算后存入緩存，否則直接返回緩存數(shù)據(jù)if cache[cur][rest] == -1:# 步數(shù)走完時，如果機器人剛好到達目標位置，則返回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]

假如:
位置數(shù) pos=6
剩余步數(shù)steps=5
開始位置start=1
目標位置target=4
cur為當前位置
創(chuàng)建動態(tài)表dp 行代表位置數(shù) pos(1,pos), 列代表剩余步數(shù)rest(0,steps)
根據(jù)遞歸條件填表：
1、當剩余步數(shù)為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

代碼實現(xiàn)

class RobotWalk(object):def ways_c(self, pos, steps, start, target):""":param pos: 總共有pos個位置:param steps: 可以走的步數(shù):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# 剩余步數(shù)rest 范圍 0~steps# steps（總步數(shù)） 列 pos（總共位置數(shù)） 行的數(shù)組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]