动态规划(一)极速入门

时间:2022-10-15 07:12:56

动态规划开胃菜

动态规划中有几个重要概念,分别是

  • 状态转移方程
  • 重叠子问题

递推与动态规划

先来做一道高中数学题
动态规划(一)极速入门

通俗来讲动态规划 算法并不直接给出最终结果的求解表达式,而是通过找到问题规模之间的 动态转移方程,借此不断缩小问题规模,逐渐迫近base case

解法一

def func(n):
    if n == 0:
        return 2
    return func(n - 1) + 3

自顶向下的计算顺序,正如上图紫线箭头方向

解法二

def func2(n):
    # 确定dp[i] 的含义
    # d[i] == func(i)
    # dp数组规模,规模与dp[i]的定义密切相关
    # 根据dp[i] 定义,func2(n) 对应dp[n]
    # 要使得dp[n] 合法,数组长度要为 n+1
    dp = [0] * (n + 1)
    # base_case
    dp[0] = 2
    # dp数组的遍历顺序
    # func(i) = func(i-1) + 3
    # dp[i] = dp[i-1] + 3
    for i in range(1, n + 1):
        dp[i] = dp[i - 1] + 3
    return dp[n]

自底向上解法,正如上图绿色箭头方向

重叠子问题

直观了解了状态转移方程后,接着来以斐波那契额数列问题为例看重叠子问题

$ F(0)=0, \quad F(1)=1,\quad F(n)=F(n-1)+F(n-2) \quad\left(n \geq 2, \quad n \in N^{*}\right) $

动态规划(一)极速入门

解法一

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

不难发现, fib(18) 被执行了两次,fib(17) 被执行了3次。fib(16) 被执行了4次。。。

计算过的问题我们不想重复计算,需要一个备忘录记录我们算过的fib(n)

解法一 + 备忘录

# 使用一个字典存储计算过得fib(n)
# n为键,fib(n) 为值
memo = {}

def fib1(n):
    # 如果备忘录中有记载,直接返回
    if n in memo.keys():
        return memo[n]
    if n == 0:
        return 0
    elif n == 1:
        return 1
    val = fib(n - 1) + fib(n - 2)
    memo[n] = val
    return val

备忘录相当于为整个递归遍历树进行了一个剪枝操作。

fib(18) 被执行了1次,fib(17) 被执行了1次。fib(16) 被执行了1次。。。

解法二

def fib2(n):
    # 确定dp[i]的含义
    # dp[i] = fib(i)
    # dp数组规模
    dp = [0] * (n + 1)
    # base_case
    dp[0] = 0
    dp[1] = 1
    # dp 数组遍历方向
    # fib(i) = fib(i-1) + fib(i-2)
    # dp[i] = dp[i-1] + dp[i-2]
    # dp[大] 依赖 dp[小]  所以先算dp[小]
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

使用dp数组自顶向下来解不存在 重叠子问题

空间开销为 O(n),不难看出,每次计算新值只依赖前面两个值。因此我们可以使用两个变量来记录,而不使用dp数组。

解法二 + 状态压缩

def fib3(n):
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return re1
    # prev初始为dp[1]
    prev = 1
    # curr初始为dp[2]
    curr = 1
    # 注意迭代次数
    # 注意i = 3时,迭代了1轮,迭代结束 curr == dp[3]
    # 注意i = 4时,迭代了2轮,迭代结束 curr == dp[4]
    # 所以 i = n 时,迭代结束时 curr == dp[n]
    # range 前闭后开 so ...
    for i in range(3, n + 1):
        sum = prev + curr
        prev = curr
        curr = sum
    return curr

总结一下,当出现重叠子问题时,自定向下的解法一需要备忘录剪枝自底向上的解法二需要状态压缩减少空间开销。

一般来说,自顶向下的方法如果不用备忘录剪枝,一般会超时。自底向上的方法不进行状态压缩一般也没事。