侧边栏壁纸
博主头像
996worker

祇園精舎の鐘の聲, 諸行無常の響き有り。

  • 累计撰写 193 篇文章
  • 累计创建 46 个标签
  • 累计收到 8 条评论

目 录CONTENT

文章目录

递归与动态规划的解题框架

996worker
2021-07-06 / 0 评论 / 0 点赞 / 251 阅读 / 4,129 字
温馨提示:
本文最后更新于 2021-07-24,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

1. Intro

我觉得递归难,但是它比较重要,尤其是在动态规划问题(求最值)等情境下经常出现。在此引入动态规划类问题的解题框架 -- 状态转移方程。

2. 动态规划问题解析

说白了,动态解析问题的一般形式就是求最值(最长递增子序列,最小编辑距离,etc),尽量最优化,其核心,无非就是穷举。

对于穷举,我们可以暴力枚举出出所有情况,但是,其实可以使用备忘录,或者DP table来优化复杂度。

当然,说说简单,其实真要写代码就难了。其实咱们想了想,是不是可以找个部分最优解,然后进行全局推广呢?我猜比较类似于贪心?即当所有子问题解法最优,则全局最优。

这时候大佬说话了,状态转移方程是个好的方法,去应对穷举。构成状态转移方程有三要素:

  • 重叠子问题:问题里的解套子问题的解,子问题的解套孙问题的解。
  • 最优子结构:子问题求出最优解。
  • 状态转移方程:从子问题状态怎么跳到父问题的状态机的。

基于fucking-algorithm, 写出状态转移方程有套路,即:

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

以下内容,将从斐波那契数列和凑零钱问题来讲解如何写出状态转移方程。

3. 案例

3.1 斐波那契数列

用斐波那契数列讨论何为重叠子问题。

如何求出斐波那契数列中任意位置的数值呢?

3.1.1 常规暴力递归

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

对于递归,画出递归树。当N为20:

今天你会发现这有大量的重复运算...如标黄的f(18)被算了两次。所以,这就是重叠子问题

试解决重叠子问题:

3.1.2 带备忘录的递归

建立备忘录,把已经算过的东西保存下来。

int fib(int N) {
    if (N < 1) return 0;
    // 备忘录全初始化为 0
    vector<int> memo(N + 1, 0);
    // 进行带备忘录的递归
    return helper(memo, N);
}
 
int helper(vector<int>& memo, int n) {
    // base case
    if (n == 1 || n == 2) return 1;
    // 已经计算过
    if (memo[n] != 0) return memo[n];
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}

试画出递归树:

蓝色框和绿色框被跳过了,备忘录实现了减枝。对树整理,得:

发现没了冗余计算,时间复杂度收缩为O(n). 不过这个是自顶向下的,不属于动态规划。
动态规划,其实是自底向上的,即直接从最底下,最简单,问题规模最小的 f(1) 和 f(2) 开始往上推,直到推到我们想要的答案 f(20)。

3.1.3 Dp table迭代方法

试进行「自底向上」的推算,即从基础情况推到高的情况。

int fib(int N) {
    if (N < 1) return 0;
    if (N == 1 || N == 2) return 1;
    vector<int> dp(N + 1, 0);
    // base case
    dp[1] = dp[2] = 1;
    // 从base开始上推
    for (int i = 3; i <= N; i++)
        // 推完还能顺便保存结果到dp table里
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[N];
}

这个和之前的备忘录类似,不过是从最基础的开始上推。
结合上述内容,引入状态转移方程

状态转移方程,其实就是一个状态机f(n)从从f(n-1)和f(n-2)相加转移来的。
其实,我们可以把上述的过程继续优化--状态压缩。显而易见地,当前状态只和前两个状态有关,所以不需要一个巨大的DP table来做备忘录。

int fib(int n) {
    if (n < 1) return 0;
    if (n == 2 || n == 1) 
        return 1;
    int prev = 1, curr = 1;
    for (int i = 3; i <= n; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

这个技巧就是所谓的「状态压缩」,如果我们发现每次状态转移只需要 DP table 中的一部分,那么可以尝试用状态压缩来缩小 DP table 的大小,只记录必要的数据,上述例子就相当于把DP table 的大小从 n 缩小到 2。

3.2 凑零钱

给你 k 种面值的硬币,面值分别为 c1, c2 ... ck,每种硬币的数量无限,再给一个总金额 amount,问你最少需要几枚硬币凑出这个金额,如果不可能凑出,算法返回 -1 。算法的函数签名如下:

// coins 中是可选硬币面值,amount 是目标金额
int coinChange(int[] coins, int amount);

比如说 k = 3,面值分别为 1,2,5,总金额 amount = 11。那么最少需要 3 枚硬币凑出,即 11 = 5 + 5 + 1。这是一个典型的求最优问题。

3.2.1 常规暴力递归

由于每种硬币数量无限,每次取硬币互相独立。即每个子问题互相独立。
试列出状态转移方程:

  1. 确定Base Case:每次取硬币,剩余目标金额amount会减少,当amount为0,需要的硬币为0,收敛。

  2. 确定状态,即父子两问题间的变量:由于硬币各种无限,所以能够变化的,只需要考虑目标金额amount的变化. 可以用状态机帮助确定状态变化,从而确定选择里的dp搭配

  3. 确定选择,即导致「状态」变化的Trigger:这里是指每选择一个硬币,就会发生amount跳变。d在不同的选择中,调用不同的dp()搭配

  4. 明确dp函数/数组定义:我们这里讲的是自顶向下的解法,所以会有一个递归的 dp 函数,一般来说函数的参数就是状态转移中会变化的量,也就是上面说到的「状态」,函数的返回值就是题目要求我们计算的量。dp(n), 参数是状态,即dp函数返回状态是n下时所产生的结果。
    就本题来说,状态只有一个,即「目标金额」,题目要求我们计算凑出目标金额所需的最少硬币数量。所以我们可以这样定义 dp 函数:

dp(n) 的定义:输入一个目标金额 n,返回凑出目标金额 n 的最少硬币数量。

试写出伪代码解题框架:

# 伪码框架
def coinChange(coins: List[int], amount: int):

    # 定义:要凑出金额 n,至少要 dp(n) 个硬币
    def dp(n):
        # 做选择,选择需要硬币最少的那个结果
        for coin in coins:
            res = min(res, 1 + dp(n - coin))
        return res

    # 题目要求的最终结果是 dp(amount)
    return dp(amount)

缺Base Case?来加当amount为0时, 所需硬币为0。当amount小于0,硬币数为-1。
状态转移方程:

def coinChange(coins: List[int], amount: int):
    # 定义:要凑出金额 n,至少要 dp(n) 个硬币
    def dp(n):
        if n == 0: return 0;
        if n < 0: return -1;
    
    # 求出最少硬币数, 初始化为极大值
    res = INFINATE_INT;
    # 每个coin为coin 的面值
    for coin in coins:
        # 子问题的结果
        int res_of_subProblem = dp(n - coin);
        # 子问题无解,过
        if res_of_subProblem == -1: continue;

        # 找最少硬币数,第二项为子问题的所需硬币+1个硬币数
        res = min(res, 1 + res_of_subProblem);
    
    return res if res != INFINATE_INT else -1
return dp(amount)

列出递归树,发现有重复计算。比如 amount = 11, coins = {1,2,5} 时画出递归树看看:

收缩状态:备忘录等...

3.2.2 带备忘录递归

def coinChange(coins: List[int], amount: int):
    # 备忘录
    memo = dict()
    def dp(n):
        # 查备忘录,避免重复计算
        if n in memo: return memo[n]
        # base case
        if n == 0: return 0
        if n < 0: return -1
        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coin)
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)
        
        # 记入备忘录
        memo[n] = res if res != float('INF') else -1
        return memo[n]
    
    return dp(amount)

3.2.3 dp table 迭代

可以自底向上使用 dp table 来消除重叠子问题,关于「状态」「选择」和 base case 与之前没有区别,dp 数组的定义和刚才 dp 函数类似,也是把「状态」,也就是目标金额作为变量。不过 dp 函数体现在函数参数,而 dp 数组体现在数组索引:

int coinChange(vector<int>& coins, int amount) {
    // 数组大小为 amount + 1,初始值也为 amount + 1
    vector<int> dp(amount + 1, amount + 1);
    // base case
    dp[0] = 0;
    // 外层 for 循环在遍历所有状态的所有取值
    for (int i = 0; i < dp.size(); i++) {
        // 内层 for 循环在求所有选择的最小值
        for (int coin : coins) {
            // 子问题无解,跳过
            if (i - coin < 0) continue;
            dp[i] = min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}

4. 总结

第一个斐波那契数列的问题,解释了如何通过「备忘录」或者「dp table」的方法来优化递归树,并且明确了这两种方法本质上是一样的,只是自顶向下和自底向上的不同而已。

第二个凑零钱的问题,展示了如何流程化确定「状态转移方程」,只要通过状态转移方程写出暴力递归解,剩下的也就是优化递归树,消除重叠子问题而已。

5. 版权声明

思路和插图来源于Github repository:fucking-algorithm。

0

评论区