从暴力递归到动态规划

last modify

• 概述

• 经典问题

  • 1. 自底向上的递归/迭代

    • 示例 1: 跳台阶 (一维)

    • 示例 2: 解码方法 (一维, "跳台阶" 变体)

    • 示例 3: N 个骰子的点数 (一维, "跳台阶" 变体)

  • 2. 多样本位置全对应的尝试模型

  • 3. 范围内的尝试模型

  • 4. 寻找业务限制的尝试模型

• 更多相关问题

• 参考资料

概述

• 从代码角度, 动态规划的实现一般都是通过迭代完成的 (递推公式); 而一般迭代过程都有与之对应的递归写法;

  这里默认动态规划都是基于迭代的实现. 实际上, 动态规划只是一种算法, 跟具体实现无关, 递归实现也是动态规划;

• 递归过程一般与人的直接思考过程更接近, 因此如果对递归结构比较熟悉, 就能更容易的写出相应解法;

  动态规划的难点是递推过程 (经验和数学能力); 递归的难点是递归结构本身;

• 递归的一个问题是如果存在重复计算, 会大幅降低性能, 此时有两个解决方法:

  1. 转换为迭代结构; 转化过程可以套用固定模板, 详见示例;

  2. 使用记忆化搜索, 即保存中间结果; 如果用 python 书写, 可以使用 functools.lru_cache 装饰器, 详见示例;

  3. 如何判断是否存在重复计算?

     将递归过程展开为树状结构，当发现某些具有相同参数的递归调用出现在多个不同节点时，说明存在重复调用；

     以斐波那契数列为例:
             f(5)
         f(4)    f(3)
     f(3) f(2)   ...

  4. 什么情况下可以使用记忆化搜索?

     这个问题的本质, 实际上是判断问题本身是不是一个动态规划问题; 能用动态规划解决的问题必须具备无后效性, 只要具备这个特性, 就可以使用记忆化搜索;

     无后效性: 某阶段的状态一旦确定, 则此后过程的决策不再受此前各种状态及决策的影响.

经典问题

• 原文总结了 4 种常见的递归过程，基本能覆盖大部分场景；

1. 自底向上的递归/迭代

• 最常见的递归模型, 一般过程:

  1. 确定初始状态 (递归基), 即 $k=0$ 时刻的状态）

  2. 假设已知 $k-1$ 及其之前时刻的状态，推导 $k$ 时刻的状态；

  有时候可能是自顶向下, 本质是一样的;

示例 1: 跳台阶 (一维)

70. 爬楼梯 - 力扣（LeetCode）

• 该模型下的一维问题几乎都是 "跳台阶" 问题的变体;

class Solution:
    def climbStairs(self, n: int) -> int:

        from functools import lru_cache

        @lru_cache
        def dfs(i):  # 爬 i 阶存在的方法数
            if i <= 1: return 1
            # 爬 i 阶的方法数 = 爬 i - 1 阶的方法数 + 爬 i - 2 阶的方法数
            return dfs(i - 1) + dfs(i - 2)

        return dfs(n)

记忆化搜索 (不使用标准库)

class Solution:
    def climbStairs(self, n: int) -> int:

        cache = dict()  # 缓存
        
        def dfs(i):
            if i in cache: return cache[i]  # 搜索"记忆"
            if i <= 1: ret = 1
            else: ret = dfs(i - 1) + dfs(i - 2)
            cache[i] = ret  # "记忆"
            return ret

        return dfs(n)

迭代写法 (无滚动优化)

class Solution:
    def climbStairs(self, n: int) -> int:
        
        dp = [0] * (n + 1)

        for i in range(n + 1):
            if i <= 1: dp[i] = 1  # if i <= 1: return 1
            else: dp[i] = dp[i - 1] + dp[i - 2]  # dfs(i - 1) + dfs(i - 2)
        
        return dp[-1]

示例 2: 解码方法 (一维, "跳台阶" 变体)

91. 解码方法 - 力扣（LeetCode）

• 有限制的 "跳台阶" 问题;

class Solution:
    def numDecodings(self, s: str) -> int:

        from functools import lru_cache

        @lru_cache
        def dfs(i):  # s[0: i+1] 的解码方法数
            # 最容易出错的点, 以 0 开头的字符串不存在相应的编码
            if i <= 0: return int(s[0] != '0')

            ret = 0
            if '1' <= s[i] <= '9':  # 如果 s[i] 在 0~9, 存在相应的编码
                ret += dfs(i - 1)  # s[i-1] == 1 和 s[i-2] 的特殊讨论
            if s[i - 1] == '1' or s[i - 1] == '2' and '0' <= s[i] <= '6':
                ret += dfs(i - 2)
            
            return ret
        
        return dfs(len(s) - 1)

迭代写法

class Solution:
    def numDecodings(self, s: str) -> int:
        
        # if s[0] == '0': return 0

        dp = [0] * (len(s) + 1)
        # dp[-1] = dp[0] = int(s[0] != '0')
        
        # 注意 i 的范围与递归中一致, 这里利用了 python 中 list[-1] 特性, 避免了下标的调整
        for i in range(-1, len(s)):
            # 下面就是把递归中的代码搬过来
            if i <= 0:  # 如果把这一段拿到循环外, 需要调整 i 的遍历范围
                dp[i] = int(s[0] != '0')
                continue
            dp[i] = 0
            if '1' <= s[i] <= '9':
                dp[i] += dp[i - 1]
            if s[i - 1] == '1' or s[i - 1] == '2' and '0' <= s[i] <= '6':
                dp[i] += dp[i - 2]
        
        return dp[len(s) - 1]

示例 3: N 个骰子的点数 (一维, "跳台阶" 变体)

剑指 Offer 60. n个骰子的点数 - 力扣（LeetCode）

• 进阶版 "跳台阶", 相当于每次能跳的步数更多;

class Solution:
    def dicesProbability(self, n: int) -> List[float]:

        def dfs(k):
            if k == 1:
                return [1] * 7

            dp_pre = dfs(k - 1)
            dp = [0] * (k * 6 + 1)

            for i in range(1 * (n - 1), 6 * (n - 1) + 1):  # n - 1 个骰子的点数范围
                for d in range(1, 7):  # 当前骰子掷出的点数 (跳的台阶数)
                    dp[i + d] += dp_pre[i]

            return dp

        dp = dfs(n)
        return [x / (6 ** n) for x in dp[n:]]

迭代写法

class Solution:
    def dicesProbability(self, n: int) -> List[float]:

        dp = [1] * 7

        for k in range(2, n + 1):
            dp_pre = dp
            dp = [0] * (k * 6 + 1)
            for i in range(1 * k, 6 * k + 1):  # n 个骰子的点数范围
                for d in range(1, 7):  # 当前骰子掷出的点数
                    if 1 * (k - 1) <= i - d <= 6 * (k - 1):
                        dp[i] += dp_pre[i - d]

        return [x / (6 ** n) for x in dp[n:]]

2. 多样本位置全对应的尝试模型

3. 范围内的尝试模型

4. 寻找业务限制的尝试模型

该类型原文只给了很难的几个例子, 感兴趣的可以去看原视频;

更多相关问题

algorithms/暴力递归与动态规划

参考资料

• 暴力递归到动态规划 - 左程云算法教程 (p52)