一、概念
动态规划（Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，具有天然剪枝的功能，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
二、训练斐波那契数
爬楼梯
买卖股票的最佳时机
198. 打家劫舍
1025. 除数博弈
303. 区域和检索 - 数组不可变
338. 比特位计数
1227. 飞机座位分配概率
2.1、回文5. 最长回文子串
413. 等差数列划分
300. 最长上升子序列
1143. 最长公共子序列(Longest Common Subsequence)
- [583.两个字符串的删除操作]
- [712.两个字符串的最小ASCII删除和]
62.不同路径
- 63.不同路径 II
- 64.最小路径和
120. 三角形最小路径和
- 931.下降路径最小和
96. 不同的二叉搜索树
- 95.不同的二叉搜索树 II
877. 石子游戏
