将一个规模大的问题转化为几个小的问题，通过解决小问题来得到整体的解。

其核心问题是问题的状态的定义与状态转移方程的求解。关键在于将重复出现的子问题在第一次求解之后就将其保存起来，以后再遇到时不用重复求解。是按照自底向上的方式计算
如题目求解的是最大/最小值，可行与否或者方案总数时考虑。
##一般步骤：

  1. 将问题分解为不同的子问题，设计状态
  2. 定义状态转移方程，找出初始状态
  3. 执行状态转移，状态转移方程的求解
  4. 求出问题的最终答案

例子

  1. 贪吃蛇游戏
  2. 找出最长的递增子序列
    nums = [1,5,2,4,3]的递增子序列有 [1,5],[1,2],[1,2,4],[1,2,3],[1,4][1,3],[2,4,[2,3]
  • 暴力枚举
  • 动态规划：记录重复的子序列，后续可减少搜索次数（记忆化搜索，带备忘录的递归、递归树的剪枝）
  1. 斐波那契数列
    • 爬楼梯