动态规划是什么
动态规划概念
（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
-动态规划是运筹学的一个分支；
-动态规划是解决多阶段决策过程最优化的一种数学方法；
-动态规划是将多阶段问题变成一系列单阶段问题，然后逐个求解的过程
动态规划基本思想
此类问题，会有多个可行方案，每个方案得到一个解，动态规划就是找到
所有可行方案中最优解。
动态规划与分治法非常类似，其基本思想就是将一个大的问题分解成若干
小问题进行求解。
但与分治法不同的是，分治法划分的子任务相互独立，而动态规划的子任
务会相互重叠，动态规划可以避免这些重叠子任务的重复计算
动态规划具有的性质
-最优子结构：一个结构如果是最优的，那么他的子结构也一定是最优的
-无后效性：未来与过去无关
-重叠子问题：空间换时间
动态规划适用情况
-最大值/最小值
-判断是否可行
-求所有方案的总数
如果遇到以上三种情况，都可以适用动态规划的方式尝试进行解答
动态规划的一般思路
1.明确状态：每个状态会对应一个最优解
2.归纳状态转移方程：可以通过历史状态推导出当前状态的方程
3.状态边界（初始值）：需要确认状态的初始值
4.明确最终结果
例题
- 不同路径 https://leetcode-cn.com/problems/unique-paths/
- 爬楼梯 https://leetcode-cn.com/problems/climbing-stairs/
- 三角形最小路径和 https://leetcode-cn.com/problems/triangle/
- 打家劫舍 https://leetcode-cn.com/problems/house-robber/
- 打家劫舍 II https://leetcode-cn.com/problems/house-robber-ii/
- 打家劫舍 III https://leetcode-cn.com/problems/house-robber-iii/
- 零钱兑换 https://leetcode-cn.com/problems/coin-change/
- 安排邮筒 https://leetcode-cn.com/problems/allocate-mailboxes/
总结
动态规划是一个非常强大的建模工具，基本上，如果一个多阶段决策
问题没有办法写成一个动态规划的模型，那么很可能无法去解决这个问题。
虽然动态规划是一种高效的方式，但是这种高效是以空间为代价来换
取时间上的高效，因为动态规划本身就蕴含着一个和暴力枚举差不多的基
础，当变量维度变大时，所需要的计算量和需要的存储空间是按几何倍数
增长的，因此受到硬件存储和算力的影响，目前还无法使用动态规划解决
特备大规模的问题，这个就是动态规划中著名的“维度诅咒”，也可以说是
“维度障碍”。
参考：
https://leetcode-cn.com/tag/dynamic-programming/
https://leetcode-cn.com/u/wuming1991/
