动态规划

解题步骤

• 明确状态
• 明确选择
• 明确状态转移方程
  • 通常状态转移方程是也给递归函数，返回值是题意中的最值，入参分别是选择列表和状态
• 写出暴力解法
• 通过备忘录实现剪枝优化（memo数组）
• 完成自顶向下的递归解法（记忆化搜索）
• 改写自底向上的迭代解法（dp数组）
• 迭代时通常可以进一步优化空间，用常量代替dp数组

tips：

• 递归函数中通常是对每个状态进行选择，写出该选择下的状态
  • eg:

  for( state1 : states1){
    for(state2 : states2){
      upadte(state)
      }
  }
  

• 自顶向下的递归函数中的入参，实际上就是自底向上dp数组中的下标索引
• dp数组的遍历顺序，由base case 和 目标位置 决定，不一定都是 i = 0 ; i ++; j =0 ;j ++这种，还有可能是斜着遍历的，参考b站labuladong 最短编辑距离视频末尾