动态规划解题核心框架 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：动态规划解题核心框架

[Lucas-ljx]

打卡

[SunnyXiaoWei]

fighting

[ChaosJohn]

太牛逼了

[wuye251]

打卡

[luckywords]

讲的易懂,谢谢

[iMinger]

mark

[rongchenlin]

找零钱问题：通熟易懂，特别是从暴力法到带备忘录的递归，顿时明白了动态规划的核心了。其实暴力法，相当于我们心中有一颗多叉树（或者是一个图），这个二叉树恰好能够用来解决这个问题，而且找零钱问题类似于是在求解多叉树的深度。特别是下面的代码：

for (int coin : coins) {
        // 计算子问题的结果
        int subProblem = dp(coins, amount - coin);
        // 子问题无解则跳过
        if (subProblem == -1) continue;
        // 在子问题中选择最优解，然后加一
        res = Math.min(res, subProblem + 1);
    }

这块，其实我的理解就是多叉树（图）的递归遍历。 那么动态规划解法（带备忘录的递归），就是利用空间（数组）来记录一些这棵树已经遍历过的结点。通过下面的代码：

if (memo[amount] != -666)
        return memo[amount];

来判断是否是已经遍历的结点。

讲得通熟易懂，点赞:+1:

[Asber777]

首先使用递归方法进行暴力求解的框架写起来, 以此确定转移方程, 然后加上数组, 再将其修改为自底向上的代码逻辑.

1. 明确 base case
2. 明确「状态」
3. 明确「选择」
4. 定义 dp 数组/函数的含义。

[miozus]

💡关于找零钱问题，备忘录模式中，memo 的初始化值的限制，虽说正常逻辑取不到的值，那么

• Arrays.fill(memo, amount + N); 这样可以吗？
  • 不可以。因为初始值是静态写死的，而子结构调用却传入变化的参数，导致直接读取备忘录了，使得 subProblem：amount+N != -1。看似吸收合并了迭代循环的要素，但失败了，完全超出预期。
• Integer.MAX_VALUE 这样极限值可以吗？
  • 不可以。因为子结构参数中 amount - coin 相减时，会被整型溢出异常。

[changzhenlin]

厉害

[InitialD1]

厉害了，大佬

[hylhLumb]

先夸一下

[saitamahang]

关于 subProblem 为什么要 +1？ 东哥：动态规划问题的关键是 dp 函数/数组的定义，你这个函数的返回值代表什么？ 答：子问题次数（硬币个数）？