fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
动态规划解题套路框架 :: labuladong的算法小抄
这里有个疑问，如果是(1，2，3，5)这四种币种，amount=18，那么amount=17的最优解是5+5+5+2，然后再加1枚1元组成18，这样用了5枚，但这并不是最优解。因为5+5+5+3=18，这是最优解。所以我觉得子问题互相独立这个说法欠妥。
@dlseal ” 回到凑零钱问题，为什么说它符合最优子结构呢？比如你想求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10 的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的硬币）就是原问题的答案。因为硬币的数量是没有限制的，所以子问题之间没有相互制，是互相独立的。“ 这句话的意思不就是 18的最优解 = 17的最优解 + 1 吗？
@argosdh dp数组(函数)的结果是用的钱币数而不是amount总值，变量(状态)才是amount总值，所以状态转移方程是min(1+dp[i-coin]，dp[i])，说的是每次做好选择的钱币数之间是互相独立
作者关于凑零钱的最优子结构描述确实有些问题，至少从读者角度是有些费解的，私以为可以这样理解这里的子问题，要凑够amount，就要选硬币，c1至ck总要至少选一个，则选每种的最小个数是1+dp[amount-ci]，我们把每种硬币都选一遍，答案即为其中的最小值
我经常看到有人搞不清楚子问题的结果为什么是加 1，而不是加硬币金额之类的。我这里统一提示一下，动态规划问题的关键是 dp 函数/数组的定义，你这个函数的返回值代表什么？搞清楚这一点，然后就知道该怎么操作这个返回值了。
子问题总数为递归树节点个数，这个比较难看出来，是 O(n^k)，总之只要是树形结构，节点个数必然是是指数级别的。每个子问题中含有一个 for 循环，复杂度为 O(k)。所以总时间复杂度为 O(k * n^k)，指数级别。
n 層 k 叉樹的節點數量應該是(k^n-1)/k-1， 為甚麼此遞歸樹，不是 O (k^n)?
@ningguo99 备忘录需要初始化为一个不会被取到的特殊值，代表还未被计算。因为 if (amount == 0) return 0; 单独处理了 0 这种情况，所以 memo 初始化为 0 也可以认为是一个特殊值。
@cillian-bao 对，感谢指正，我改下。高度为 h 的满 k 叉树，最后一层节点数为 k^(h-1)，总的节点数应该为 k^h - 1。
“回到凑零钱问题，为什么说它符合最优子结构呢？假设你有面值为 1, 2, 5 的硬币，你想求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10, 9, 6 的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的硬币），求个最小值，就是原问题的答案。因为硬币的数量是没有限制的，所以子问题之间没有相互制，是互相独立的。” 括号里的“再选一枚面值为1的硬币”，感觉描述有些问题，应该是在子问题的基础之上选一枚能满足原问题的面值硬币，比如10,9,6最少硬币数是子问题6的硬币数目，那么这里应该选面值为5的硬币。虽然我能理解作者能表达的意思~但第一次读到这还是困惑了很久。
