解决哪类问题

:::success 动态规划的一种实现方式（另外一种是递推），搜索过程中需要记忆某些状态便于后续复用
在求解动态规划的问题时，记忆化搜索和递推，都确保了同一状态至多只被求解一次。而它们实现这一点的方式则略有不同：递推通过设置明确的访问顺序来避免重复访问，记忆化搜索虽然没有明确规定访问顺序，但通过给已经访问过的状态打标记的方式，也达到了同样的目的。
与递推相比，记忆化搜索因为不用明确规定访问顺序，在实现难度上有时低于递推，且能比较方便地处理边界情况，这是记忆化搜索的一大优势。但与此同时，记忆化搜索难以使用滚动数组等优化，且由于存在递归，运行效率会低于递推。因此应该视题目选择更适合的实现方式。 :::

代码模板

  • 思路
    • 定义状态/状态数组和状态表示含义
    • 函数f判断状态是否满足条件执行后续搜索逻辑
    • f的逻辑：更新过状态，则直接返回；没更新过状态，则更新
  • 方法
    • 法1：对暴搜DFS优化（改成“无需外部变量”的DFS然后添加记忆化数组）
    • 法2：把DP状态和方程写出来，根据它们写出DFS函数，然后添加记忆化数组
      1. int dfs(int pos, int tleft) {
      2. if (mem[pos][tleft] != -1)
      3.    return mem[pos][tleft];  // 已经访问过的状态，直接返回之前记录的值
      4. if (pos == n + 1) {
      5.    mem[pos][tleft] = 0;
      6.    return 0;
      7. }
      8. int res1 = dfs(pos + 1, tleft);
      9. int res2 = Integer.MIN_VALUE;
      10. if (tleft >= tcost[pos])
      11.    res2 = dfs(pos + 1, tleft - tcost[pos]) + mget[pos];  // 状态转移
      12. mem[pos][tleft] = Math.max(res1, res2);  // 最后将当前状态的值存下来
      13. return mem[pos][tleft];
      14. }

      复杂度

      O(所有节点的规模)

      运用思想

      递归

      例题

      | 题目 | 难度 | 推荐指数 | | —- | —- | —- | | 87. 扰乱字符串 | 困难 | 🤩🤩🤩 | | 375. 猜数字大小 II | 中等 | 🤩🤩🤩🤩🤩 | | 403. 青蛙过河 | 困难 | 🤩🤩🤩🤩 | | 494. 目标和 | 中等 | 🤩🤩🤩🤩 | | 552. 学生出勤记录 II | 困难 | 🤩🤩🤩🤩 | | 576. 出界的路径数 | 中等 | 🤩🤩🤩🤩 | | 913. 猫和老鼠 | 困难 | 🤩🤩🤩🤩 | | 1137. 第 N 个泰波那契数 | 简单 | 🤩🤩🤩🤩 | | 剑指 Offer 10- I. 斐波那契数列 | 简单 | 🤩🤩🤩🤩🤩 |

参考

https://oi-wiki.org/dp/memo/