记忆化搜索

常见的记忆化key方案

常用技巧

• 得先想出递归的完整方案
• 将递归的参数引入记忆化搜索中
• 记忆化搜索key压缩技术

经典题目

• 3154. 到达第 K 级台阶的方案数

  • 想到了递归方案 -> 但是边界条件的处理不适合转化为记忆化
    • 想到的递归没有带返回值
  • 但是没有想出如何进行递归化搜索
  • 边界条件处理的逻辑
  • 还是子问题的逻辑没有想好

• 3144. 分割字符频率相等的最少子字符串

  • 记忆化递归的过程比较容易想到
  • 难点在于：如何在遍历的过程中进行字串是否平衡的判断
    • 平衡：字串长度 = 字符种类✖️字符出现的最大次数