【传统算法】复杂问题转换与简单问题梳理

本文章还未完成最终梳理，内容持续更新中。

把复杂问题转换为多个简单问题的叠加

什么样的算遇到复杂问题了？

按照正向思考方向来说，细节会变得极其的多与复杂，比如918.环形子数组的最大和，若按已有体系下的思路，则是：dp设计为以i为结尾且必包含i的，遍历走两遍nums，且需要记住最大结果时的子数组开头位置，这样才不会重复。如此一来，逻辑和细节就变得非常复杂了。

什么样的问题是能被转换的？如何化整为零？

熟悉自己以前做过的简单题类型，思考当前题目可以拆成以前什么简单题的什么组合
自己归纳了一下目前常见的简单题分支：

• 求和/最大值/最小值：
  • 按状态转移的模式分：
    • 必须连续（=子数组）
      • 一维：53.子数组最大和、5.最长回文子串
      • 二维：64.矩阵最小路径和
    • 可以断开（=子序列）
      • 一维：516.最长回文子序列、300.最长递增子序列、198.打家劫舍
      • 二维：72.编辑距离
  • 按状态转移的方向分：
    • 从左到右：以上各题
    • 从右到左：
  • 按单元结构的类型分：
    • 单元结构为数字：以上各题
    • 单元结构非数字：1027.最长等差数列
  • 按整体结构的类型分：
    • 整体结构为数组：以上各题
    • 整体结构为字典：1218.最长定差子序列
    • 整体结构为树：
• 求方案数量：
  • 139.单词拆分
  • 673.最长递增子序列的个数
  • 70.爬楼梯