动态规划算法

在分治算法的过程当中，分为若干个子问题有时候是完全相同的，我们只需要把它存储起来，用到的时候在查找提取，可以大大优化算法的时间复杂度

解决动态规划的一般步骤

1. 识别动态规划特征
   • 最优子结构：问题的最优解可以由子问题的最优解有效的构造出来
   • 重叠子问题：许多相同的子问题会被重复计算
2. 定义状态：通常用数组（一维二维）来表示某个特定阶段的解。
   • 例如dp[i]表示爬楼梯问题中，爬到第i层的解
3. 推导状态方程：爬楼梯问题，例如dp[i]=dp[i−1]+dp[i−2]
4. 确定初始状态/递归出口
5. 确定计算顺序：自上而下/自下而上

示例： 矩阵链乘问题 最长公共子序列 0 1背包问题

reference