知识点

1. 动态规划问题

   1. 什么是动态规划问题

      动态规划的问题，一般形式都是求最值问题，例如：求最长递增子序列呀，最小编辑距离等等

      重叠子问题、最优子结构、状态转移方程就是动态规划三要素，其中，最重要的就是写出状态转移方程

      状态转移方程如何思考：明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case

LeetCode算法

1. LeetCode算法

   1. 322.【零钱兑换】

      解题思路：

      要求最少的零钱数，因为是求最值问题，因此优先考虑是否为动态规划问题。

      因为凑零钱的子问题符合最优子结构，即每个子问题之间相互独立互不约束并且子问题的最优解可以推出题目的解，因此这个问题就是个动态规划问题

      既然是动态规划问题，因此必须要找到动态转移方程。首先确定状态，在该问题中，因为硬币是无限的，因此硬币不是状态，唯一的状态就是目标金额；然后确定f(n)的含义，f(n)含义是，如果目标金额为n，则f(n)就是至少需要f(n)个硬币凑出金额；然后确定「选择」并择优，对于不同的目标金额，都是从零钱堆中取出不同面值的零钱来凑，因此不同的硬币面值就是选择；最后明确 base case，当目标金额为 0 时，所需硬币数量为 0；当目标金额小于 0 时，无解，返回 -1