哔哩哔哩：
第一个版本对动态规划的理解
# 问题有大量的重复问题，比如求feibolaqie(5) = feibolaqie(4)+feibolaqie(3), # 所以有重复问题，通过缓存优化，把以前求过的问题做缓存 # def feibolaqie(n): # if n ==1: # return 1 # elif n==2: # return 1 # else: # return feibolaqie(n-1)+feibolaqie(n-2) # print(feibolaqie(7)) # 题目有个机器人，在步长为n的数组中，从开始start位置，走K步到aim位置 # def ways(n, start, aim, k): # return process(start, aim, k, n) # # # def process(cur, aim, rest, n): # if rest == 0: # return 1 if cur == aim else 0 # if cur == 1: # return process(2, aim, rest - 1, n) # elif cur == n: # return process(n - 1, aim, rest - 1, n) # else: # return process(cur - 1, aim, rest - 1, n) + process(cur + 1, aim, rest - 1, n) # 使用缓存对递归经行问题优化,傻缓存法 # def ways1(n, start, aim, k): # # 定义一个[n+1][k+1]的二维数组初始话为-1表示数据没有被复制,这里要用N因为可以走回去 # dp = [[-1 for i in range(k+1)] for j in range(n+1)] # return process1(start, aim, k, n, dp) # # # def process1(cur, aim, rest, n, dp): # if dp[cur][rest] != -1: # return dp[cur][rest] # ans = 0 # if rest == 0: # ans = 1 if cur == aim else 0 # elif cur == 1: # ans = process1(2, aim, rest - 1, n, dp) # elif cur == n: # ans = process1(n - 1, aim, rest - 1, n, dp) # else: # ans = process1(cur - 1, aim, rest - 1, n, dp) + process1(cur + 1, aim, rest - 1, n, dp) # dp[cur][rest] = ans # return ans # 动态规划解决问题 def ways2(n, start, aim, k): # 定义一个[n+1][k+1]的二维数组初始话为-1表示数据没有被复制,这里要用N因为可以走回去,全部定义为0因为rest为0的时候只有目标值为1 dp = [[0 for i in range(k + 1)] for j in range(n + 1)] # 只需要填充退出条件为rest = 0，因为rest为0的时候只有目标值为1 dp[aim][0] = 1 # 填充dp for rest in range(1, k + 1): dp[1][rest] = dp[2][rest - 1] for cur in range(2, n): dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1] dp[n][rest] = dp[n - 1][rest - 1] return dp[start][k] print(ways2(5, 2, 4, 6))