动态规划解题套路框架 :: labuladong的算法小抄

[utterances-bot]

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

评论礼仪 见这里，违者直接拉黑。

[jizhigang]

哇！真是太奇妙了，虽然我没看懂

[xvyaxi]

想知道dong哥画图用的什么工具

[argosdh]

这里有个疑问，如果是(1，2，3，5)这四种币种，amount=18，那么amount=17的最优解是5+5+5+2，然后再加1枚1元组成18，这样用了5枚，但这并不是最优解。因为5+5+5+3=18，这是最优解。所以我觉得子问题互相独立这个说法欠妥。

[wang1000001000]

你理解错了，你说的这个不是子问题的最优解，按照你那个来说，下一个最优子问题可能是18-3 = 15，或者是18 - 5 = 13，不是18 - 1 = 17

[labuladong]

你理解错了。计算 dp(amount = 18) 的最优解时，会穷举所有可能，即计算 min(dp(18-1), dp(18-2), dp(18-3), dp(18-5)) 取出最小值再 + 1，这就可以得到你说的 5+5+5+3=18 这个最优解。

再具体点说，你所说的这个 5+5+5+2+1 = 18 的方案，会在计算 min 时被抛弃，计算 min 时会选择 5+5+5+3=18，因为这个方案所需的硬币数最少。

[daydaystudylab]

@argosdh 你理解错了，你说的只是其中一种情况

[dlseal]

@argosdh 18的最优子解，不一定是17的最优解

[coder-pig]

牛啊牛啊

[yancewang]

@argosdh 5+5+5+3的情况在dp(18-3)里面了

[jiangshiyong1]

@dlseal ” 回到凑零钱问题，为什么说它符合最优子结构呢？比如你想求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10 的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的硬币）就是原问题的答案。因为硬币的数量是没有限制的，所以子问题之间没有相互制，是互相独立的。“ 这句话的意思不就是 18的最优解 = 17的最优解 + 1 吗？

[wang1000001000]

子问题的答案加一不是再选一枚面值为1的硬币，而是再加一次减相应硬币的操作，那1，3，5都是加1，我们这个问题是算操作数，不是算硬币数，

[Money8888]

@argosdh dp数组(函数)的结果是用的钱币数而不是amount总值，变量(状态)才是amount总值，所以状态转移方程是min(1+dp[i-coin]，dp[i])，说的是每次做好选择的钱币数之间是互相独立

[spadan]

作者关于凑零钱的最优子结构描述确实有些问题，至少从读者角度是有些费解的，私以为可以这样理解这里的子问题，要凑够amount，就要选硬币，c1至ck总要至少选一个，则选每种的最小个数是1+dp[amount-ci]，我们把每种硬币都选一遍，答案即为其中的最小值

[a572251465]

666 还需要多多练习啊

[daifaming-0107]

凑零钱的最优子结构描述 读者理解起来很费解。我和上面几位同学有相同的疑问？ 可能还是没深刻理解

[diandengpao]

作者的意思就是子问题间互相独立。
即求 f(amount = 11) 时(原问题)，要证明子问题f(10), f(9), f(6)是互相独立的。
也就是要证明 f(10)的最少硬币数 不能影响 f(9)的最少硬币数。

[labuladong]

我经常看到有人搞不清楚子问题的结果为什么是加 1，而不是加硬币金额之类的。我这里统一提示一下，动态规划问题的关键是 dp 函数/数组的定义，你这个函数的返回值代表什么？搞清楚这一点，然后就知道该怎么操作这个返回值了。

[zzuuoo]

一定有面值为1的硬币吗？

[SuperJiang1998]

.同问，里面都是数组了，不应该假设一定有硬币 1 的情况吧

[morganwu277]

当然不一定

[zzuuoo]

😯 懂了 ，忽略忽略

[Yuzong-LYZ]

斐波那契，备忘录，看不太懂，但是dp看的懂

[wen-shuai]

看了文章之后，独立刷出来了。赞！！

[night-crow1995]

aaa

[Andy-zz-zz]

有点刻意秀递归了，像硬币这种题，关键怎么知道是二元dp问题，什么时候是一元dp问题，子问题怎么找的就一笔带过，这部分真不如去看 leecode 官解

[kebwlmbhee]

暴力遞歸的空間複雜度也是 O(n) 嗎？

[aerocraft696]

回到凑零钱问题，为什么说它符合最优子结构呢？假设你有面值为 1, 2, 5 的硬币，你想求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10, 9, 6 的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1, 2, 5 的硬币），求个最小值，就是原问题的答案。因为硬币的数量是没有限制的，所以子问题之间没有相互制，是互相独立的。
作者，我认为这句话最后一句认为不对，硬币数量有限制时，子问题之间并没有制约，只是由于自身制约造成的。

[JeanYang2]

322零钱兑换Python版打卡

class Solution:
    def dp(self,memo,amount,coins):
        if amount==0:
            return 0
        if amount<0:
            return -1
        if memo[amount]!=1000:
            return memo[amount]
        res=float('inf')
        for coin in coins:
            subProblem=self.dp(memo,amount-coin,coins)
            if subProblem==-1:
                continue
            res=min(res,subProblem+1)
        memo[amount] = -1 if res == float('inf') else res
        return memo[amount]

    def coinChange(self, coins: List[int], amount: int) -> int:
        memo=[1000]*(amount+1)
        return self.dp(memo,amount,coins)

[bugsyyu]

子问题总数，严格来讲应该是递归树的【中间】节点个数吧？不包括叶节点

[Chenxianzhi]

dp解法明白。但是备忘录解法原理能明白，代码却像天外来物，暂时还不能内化。感谢博主，收获颇丰。

[GeorgeSmith215]

自底向上动规js解法
function jump(nums: number[]): number {
const n = nums.length
const dp = new Array(n).fill(n)
// base case
dp[n-1] = 0
for (let i = n - 2; i >= 0; i--) {
for (let j = 1; j <= nums[i]; j++) {
if (i + j >= n) break
dp[i] = Math.min(dp[i], dp[i + j] + 1)
}
}
return dp[0]
};

[GeorgeSmith215]

发错地方了，应该是这里的：
https://labuladong.github.io/algo/di-er-zhan-a01c6/tan-xin-le-9bedf/ru-he-yun--48a7c/#jump-game-ii

[Andywjw]

有读研的还不会的么

[DengQ]

这2个例子理解入门挺好的，学习了

[HCWGH]

凑硬币

    //dpArray表示凑齐amount所需最少硬币个数
    //状态转移方程 dp[i]=dp[0...coins]
    public int dpArray(int[]coins,int amount){
      int[]dp=new int[amount+1];
      for(int i=1;i<=amount;i++){
        dp[i]=Integer.MAX_VALUE;
        for(int j=0;j<coins.length;j++){
          int val=coins[j];
          //由0--i-1的去凑
          if(i-val>=0&&dp[i-val]>=0){
           dp[i]=Math.min(dp[i-val]+1,dp[i]);
          }
        }
        dp[i]=dp[i]==Integer.MAX_VALUE?-1:dp[i];
      }    
      return dp[amount]; 
    }

[qinmianer]

想请教一下大家为什么凑零钱问题不能用贪心算法来解？我第一感觉是贪心，因为想要硬币数最少，那就总是先使用面额大的硬币来凑？

[chl64]

【coinChange 代码分析 & 提议】

本文代码：

int coinChange(int[] coins, int amount) {
    // 题目要求的最终结果是 dp(amount)
    return dp(coins, amount)
}

// 定义：要凑出金额 n，至少要 dp(coins, n) 个硬币
int dp(int[] coins, int amount) {
    // base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;

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

    return res == Integer.MAX_VALUE ? -1 : res;
}

上述代码里的 if (subProblem == -1) continue; 判断，其实处理了两个无解场景：
1、子问题 int subProblem = dp(coins, amount - coin) 因 amount < coin 而无解。
2、当前问题 dp(coins, amount) 里，因 for 循环的全部 coin 都无解，所以 return res == Integer.MAX_VALUE ? -1 : res; 向上层 recursion 返回 -1。

万一以为此判断只处理了场景1，不用数值-1来识别（例如改用-100），则无法处理场景2：

int dp(int[] coins, int amount) {
    ...
    if (amount < 0) return -100;

    int res = Integer.MAX_VALUE;
    for (int coin : coins) {
        int subProblem = dp(coins, amount - coin);
        if (subProblem == -100) continue;
        ...
    }

    return res == Integer.MAX_VALUE ? -1 : res;
}

可读性更高的写法，是进入recursion前就以 if (amount >= coin) 避免场景1；返回 MAX_VALUE 就代表场景2：

int coinChange(int[] coins, int amount) {
    int res = dp(coins, amount)
    return res == Integer.MAX_VALUE ? -1 : res;
}

int dp(int[] coins, int amount) {
    if (amount == 0) return 0;

    int res = Integer.MAX_VALUE;
    for (int coin : coins) {
        if (amount >= coin) {
            int subProblem = dp(coins, amount - coin);
            res = Math.min(res, subProblem + 1);
        }
    }

    return res;
}

[Pagliuca-git]

东哥，递推解法框架是不是应该修改为下面的样子，原文应该是笔误了

• 自底向上迭代的动态规划

• 初始化 base case

• dp[0][0][...] = base case

• 进行状态转移

• for 状态 in 所有可能的状态：

• for 选择 in 所有可能的选择：
  

•     for ...
  

•         dp[状态1][状态2][...] = 求最值(状态1，状态2...)