We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see ourdocumentation.
There was an error while loading.Please reload this page.
1 parentc1fb14e commit0052e3fCopy full SHA for 0052e3f
problems/322.coin-change.md
@@ -21,9 +21,8 @@ You may assume that you have an infinite number of each kind of coin.
21
```
22
##思路
23
24
-可以用动态规划来写， 可以先画一个二维表，然后观察，其是否可以用一维表代替。
25
26
-也可以暴力分析，我们把coin逆序排列，然后逐个取，取到刚好不大于amout，依次类推。
+假如我们把coin逆序排列，然后逐个取，取到刚好不大于amout，依次类推。
27
28
29
eg: 对于 [1,2,5] 组成 11 块
@@ -46,6 +45,16 @@ eg: 对于 [1,2,5] 组成 11 块
46
45
47
因此结果是 3
48
+
49
+熟悉贪心算法的同学应该已经注意到了，这就是贪心算法，贪心算法更amount尽快地变得更小。
50
+`经验表明，贪心策略是正确的`。 注意，我说的是经验表明， 贪心算法也有可能出错。 就拿这道题目来说，
51
+他也是不正确的！ 比如`coins = [1, 5, 11] amout = 11`, 因此这种做法有时候不靠谱，我们还是采用靠谱的做法.
52
53
+如果我们暴力求解，对于所有的组合都计算一遍，然后比较， 那么这样的复杂度是 2 的 n 次方（这个可以通过数学公式证明，这里不想啰嗦了），
54
+这个是不可以接受的。那么我们是否可以动态规划解决呢？答案是可以，原因就是可以划分为子问题，子问题可以推导出原问题
55
56
+对于动态规划我们可以先画一个二维表，然后观察，其是否可以用一维表代替。
57
+关于动态规划为什么要画表，我已经在[这篇文章](../thinkings/dynamic-programming.md)解释了
58
##关键点解析
59
60
- 动态规划
