简介
动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。 -- 百度百科
从上面的介绍可以看出，动态规划就是为了求解最优。
适用条件：
- 最优化原理（最优子结构）
简单来说就是一个最优化的策略的子策略总是最优的。
- 无后效性
简单来说就是每个状态都是过去历史的一个完整总结。
- 子问题的重叠性（重叠子问题）
在解决最终问题的过程，多次出现了重复计算。
# 爬楼梯
题目描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
通过递归实现：
通过记忆优化搜索实现：
通过动态规则实现：
# 最少的硬币数目
题目描述：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例1：
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例2：
输入: coins = [2], amount = 3
输出: -1
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gaM7Ch
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
什么时候使用动态规则呢？
- 一个题要求给出达成某个目的的解法个数。
- 不要求给出每一种解法的对应的具体路径。
- 最值问题等可以尝试动态规则。
动态规则分析路径：
- 递归思想明确树形思维模型：找到问题终点，思考倒退的姿势，往往可以帮助你更快速地明确状态间的关系
- 结合记忆化搜索，明确状态转移方程
- 递归代码转化为迭代表达（这一步不一定是必要的，1、2本身为思维路径，而并非代码实现。若你成长为熟手，2中分析出来的状态转移方程可以直接往循环里塞，根本不需要转换）。
动态规则的概念理解起来一点都不难，难的是遇到问题后怎么建模，怎么思考，很多时候即便你知道了
动态规则可以理解成一种聪明的递归。
就好比，你知道了很多道理，但依然过不好这一生。
动态规划一定是让求最值的，它的核心是穷举。
动态规划特点：
- 重叠子问题
- 状态转移方程
- 最优子结构
重叠子问题和最优子结构可以看做是动态规划的一个特性，只要一个题能看到这两个，就说明可以使用动态规划，状态转移方程是解题的核心，也就是通过状态转移方程去穷举的。
解题套路：
- 明确状态（状态指的是会变的，如果dp函数的参数，或者dp数组的索引）
- 明确选择
- 明确db函数/数组的定义
- 明确 base case
如何穷举？
写出状态转移方程，暴力穷举所有可行解。
如何聪明的穷举？
用备忘录消除重叠子问题，写出自顶向下解法。进一步，可以写出自底向上的迭代解法。再进一步可以优化空间复杂度。
← 排序算法