【文件属性】：
文件名称：leetcode下载-leetCode-js:leetCode-js
文件大小：12KB
文件格式：ZIP
更新时间：2021-06-29 19:50:21
系统开源
leetcode下载
动态规划：尝试分解子问题
在研究了好几天，看了大佬们无数的解题思想之后，我终于明白了动态规划的本质，其实理解
一个算法的思想，有很多时候只差临门一脚，希望我的题解能帮助到大家。
我们经常听到「最优子结构」「缩小问题规模」「自顶向下」「自底向上」等跟动态规划
相关的词汇。
接下来就彻底搞懂这种思想，顺带着我自己也重温一遍刚刚搞懂的喜悦。
----------------开始解题，拿实例来说话----------------------
假设给出的不同面额的硬币是[1,
2,
5]，目标是
120，问最少需要的硬币个数？
我们要分解子问题，分层级找最优子结构，看到这又要晕了哈，憋急~~
下面马上举例。
这里我们使用「自顶向下」思想来考虑这个题目，然后用「自底向上」的方法来解题，
体验算法的冰火两重天。
dp[i]:
表示总金额为
i
的时候最优解法的硬币数
我们想一下：求总金额
120
有几种方法？下面这个思路关键了
!!!
一共有
3
种方式，因为我们有
3
种不同面值的硬币。
1.拿一枚面值为
1
的硬币
+
总金额为
119
的最优解法的硬币数量
这里我们只需要
【文件预览】：
leetCode-js-master
----.gitignore(13B)
----package.json(865B)
----.vcmrc(42B)
----.czrc(39B)
----CHANGELOG.md(1KB)
----.huskyrc(60B)
----.eslintrc.js(502B)
----.prettierrc.js(1KB)
----README.md(4KB)
----.autocommitrc(30B)
----leetCode.html(20KB)
----.lintstagedrc(123B)