这是一个动态规划问题,通常解决并理解一个动态规划问题需要以下 4 个步骤:

  1. 利用递归回溯解决问题
  2. 利用记忆表优化(自顶向下的动态规划)
  3. 移除递归的部分(自底向上的动态规划)
  4. 使用技巧减少时间和空间复杂度
  5. 如何估算时空复杂度