动态规划基础：树型 DFS、回溯与记忆化搜索

1. 基础与示范

回溯和记忆化搜索是动态规划的基础，本文只讲回溯 + 记忆化解决动态规划问题。要记住任何的回溯都应看作树，所以动态规划也可以当作树来求解。实际上动态规划的推导步骤就是：

• 回溯 --> 回溯 + 记忆化 --> 递推公式。

递归有自顶向下和自底向上两种写法，但是自底向上更适合记忆化，因为：

• 自顶向下过程中常用全局变量和参数传递信息，常常无返回值，记忆化数组的原理是当前节点到递归终止的最优解。当记忆到这个最优解时，当前路径的**'递'这一过程就结束了，如果还需要'归'**，那么递归函数就需要返回值，就成为有递有归或自底向上了。

记忆化的核心与原理就是：

• 当前从某个子节点（一般是叶子结点）'归'到某个根节点这个路径的信息已经有了，其他子节点归到某个根节点时，可能也会用到同样的信息，于是直接拿来用跳过'归'的过程。

下面从递归 + 回溯到记忆化搜索进行基础例题讲解。

1.1 70.爬楼梯 自顶向下

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

该题是非常基础的题，我们单纯将其当作树进行处理：

• 每个节点下面有两个节点，分别是走一步和走两步
• 递归终止条件是走到了 n
• 没有显示恢复现场，是因为我们用自顶向下传递当前走到的步数，直接在参数中进行更改
• **有递无归：**根节点是 0 表示从第 0 步开始，叶子结点是 n 表示走到了第 n 步

class Solution { public: int climbStairs(int n) { int ans = 0; auto dfs = [&](this auto&& dfs, int cur) -> void { if(cur == n){ ans += 1; return; } if(cur > n) return; dfs(cur + 1); dfs(cur + ); }; ();  ans; } };