一、大数乘法
1、大数乘法，为什么需要用字符串存储？
- 因为很大的数据很容易发生溢出问题，所以要用字符串进行存储。
2、简述大数乘法的核心思想？
image.png
image.png
3、上述大数乘法还可以进行优化吗？
image.png
- 后续有空，自己动手计算下时间复杂度的变化，才能体会到优化的思想精髓
- 其实优化也是采取分支的思想
- 将 4T(n/2) 降低到了 3T(n/2)
二、动态规划开篇
1、动态规划英文名称是什么？动态规划是解决什么问题的常用策略？
- 动态规划（Dynamic Programming），简称 DP。
- 是求解
最优化问题的一种常用策略。 - 一般带有 “最” 字的问题，都可以尝试用动态规划来解决。
image.png
2、动态规划的通常使用套路是什么（新手三步曲）？
- ①暴力递归（自顶向下，会出现重复子问题）
- ②记忆化搜索（自顶向下）
- ③递推（自底向上）
image.png
3、使用动态规划的思想，来解决零钱兑换的问题？（结合例子理解动态规划）
image.png
4、按照上面的核心思路，如何进行代码实现？
- 太强了，五行代码就解决了。暴力递归的代码真的很精简啊~~~
- 暴力递归是自顶而下的思维方式
image.png
5、暴力虽美，但是效率很低。上述代码存在什么问题？
- 一个函数里面，调用了四个子函数（是否想起斐波那契数列的恐怖递归😱）
- 比如计算 coins(4) ，每次都需要重复计算 coins(3)、coins(2)、coins(1)，这样的重复大量存在，损耗性能
- 思考如何解决重复计算的问题呢？
6、接下来我们对暴力递归进行优化，使用记忆搜索法（依然自顶向下的调用）
image.png
7、为什么我们会觉得上面的算法可以使用递推（自底向上）优化？
- 因为我们分析上述代码计算过程，发现都是先计算出小值的最优解，然后再计算n的最优解。
- 那么我们有理由相信是可以从小的值开始迭代，计算出大的值。
image.png
8、上述代码时间复杂度，空间复杂度都是多少？
image.png
9、如果要求出具体选的哪几枚硬币要怎么办？
image.png
10、 如果硬币组合和零钱数都是可变的，凑不齐返回-1，如何设计代码？（通用的实现）
- 先思考外部如何调用，再思考内部如何实现
image.png
