简称DP
是求解最优化问题的一种常用策略
通常的使用套路（适合新手）
1.暴力递归（自顶向下，出现了重叠子问题）
2.记忆化搜索（自顶向下）
3.递推（自底向上）
常规步骤：（专业）
1.定义状态（状态是原问题，子问题的解）
比如定义dp[i]的含义
2.设置初始状态
比如设置dp[0]的值
3.确定状态转移方程
比如确定dp[i]和dp[i-1]的关系
可以用动态规划来解决的问题，通常具备2个特点
1.最优子结构（最优化原理）：通过求解子问题的最优解，可以获得原问题的最优解
2.无后效性
某阶段的状态一单确定，则此后过程的演变不再受此前各种状态及决策的影响
在推导后面阶段的状态时，只关心前面阶段的具体状态值，不关心这个状态是一步一步推导出来的
使用动态规划解决相关问题
1.花硬币
2.背包问题
3.最长公共子序列
4.最长公共子串
5.最长上升子序列
6.最大子串和
7.礼物的最大价值
8.买卖股票的最佳时机
9.编辑距离
