左程云动态规划问题学习（python版本重写）

哔哩哔哩：

6.二次优化(3)_哔哩哔哩_bilibili

第一个版本对动态规划的理解

# 问题有大量的重复问题，比如求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))