[算法] 动态规划

两大条件：

1. 重复子问题
   判断：同一问题的各个子问题是独立的，彼此不共享资源；但不同问题的子问题是重叠的
   带备忘录的递归方法
   使用一个数组记录 先判断数组是否已计算过
2. 最优子结构
   判断：反证法，假设子问题的解 不是最优解那么通过cut子问题paste最优解一定可以得出原问题一个更好的解从而退出矛盾

四步求解：

• 分析最优解的结构
• 递归定义最优解的值
  （最优解通常需要做出选择，思考时要假设选择中用到的子问题已经被解决）
• 自底向上计算最优解的值
  判断二维(一维)数组求解方向
• 自顶向下递归构造最优解

时间复杂度为：子问题的总个数 * 每个子问题有多少种选择，空间复杂度即子问题的个数
根据子问题的数目和每个子问题依赖其他子问题的个数可以划分四类tD/eD方程：

1. 1D/1D
   已知D[0]，状态转移方程为
   LIS最长递增总序列
   钢条切割
   整齐打印
   最大连续子数组和/乘积

2. 2D/0D
   已知D[i,0]和D[0,j]，状态转移方程为
   LCS最长公共子序列
   最长回文子序列
   字符串编辑距离
   二维矩阵最优路径

3. 2D/1D
   已知D[i,i]=0，状态转移方程为
   BST最优二叉搜索树
   矩阵链乘

4. 2D/2D
   已知D[i,0]和D[0,j]，状态转移方程为
   上述方程中的D[i,j]都可根据E[i,j]在常数时间内算出来

常见的DP类型

数位DP

数位DP通常用于解决两个整数a，b之间存在多少满足某个条件的数（且条件与数字每一位有关）的问题。
假设给定数x，包含n位，表示为，那么当我们求解n位数字的状态所对应的答案时就需重复计算n-1位数字的状态所对应的答案，因此具有重复子问题。
考虑DP状态为dp(idx, tight, sum)