动态规划

引入

[!NOTE] 爬楼梯
给定一个共有 𝑛 阶的楼梯，你每步可以上 1 阶或者 2 阶，请问有多少种方案可以爬到楼顶。

如图所示，对于一个 3 阶楼梯，共有 3 种方案可以爬到楼顶。

暴力搜索:回溯

我们可以考虑通过回溯来穷举所有可能性。具体来说，将爬楼梯想象为一个多轮选择的过程：从地面出发，每轮选择上 1 阶或 2 阶，每当到达楼梯顶部时就将方案数量加 1 ，当越过楼梯顶部时就将其剪枝。

/*回溯*/
void backtrack(vector<int> &choices, int state, int n, vector<int> &res) {
	// 当爬到第 n 阶时，方案数量加 1
	if (state == n)
		res[0]++;
		// 遍历所有选择
	for (auto &choice : choices) {
	// 剪枝：不允许越过第 n 阶
		if (state + choice > n)
			break;
	// 尝试：做出选择，更新状态
		backtrack(choices, state + choice, n, res);
	// 回退
		}
	}
	/* 爬楼梯：回溯 */
int climbingStairsBacktrack(int n) {
	vector<int> choices = {1, 2}; // 可选择向上爬 1 或 2 阶
	int state = 0;
	// 从第 0 阶开始爬
	vector<int> res = {0};
	// 使用 res[0] 记录方案数量
	backtrack(choices, state, n, res);
	return res[0];
}

暴力搜索:深度优先搜索

我们可以根据递推公式得到暴力搜索解法。以 𝑑𝑝[𝑛] 为起始点，递归地将一个较大问题拆解为两个较小问题的和，直至到达最小子问题 𝑑𝑝[1] 和 𝑑𝑝[2] 时返回。其中，最小子问题的解是已知的，即 𝑑𝑝[1] = 1、𝑑𝑝[2] = 2 ，表示爬到第 1、2 阶分别有 1、2 种方案。

/* 搜索 */
int dfs(int i) {
	// 已知 dp[1] 和 dp[2] ，返回之
	if (i == 1 || i == 2)
		return i;
	// dp[i] = dp[i-1] + dp[i-2]
	int count = dfs(i - 1) + dfs(i - 2);
	return count;
}
/* 爬楼梯：搜索 */
int climbingStairsDFS(int n) {
	return dfs(n);
}

重叠子问题

指数阶的时间复杂度是由于“重叠子问题”导致的。例如 𝑑𝑝[9] 被分解为 𝑑𝑝[8] 和 𝑑𝑝[7] ，𝑑𝑝[8] 被分解为 𝑑𝑝[7] 和 𝑑𝑝[6] ，两者都包含子问题 𝑑𝑝[7] 。

记忆化搜索

为了提升算法效率，我们希望所有的重叠子问题都只被计算一次。为此，我们声明一个数组 mem 来记录每个子问题的解，并在搜索过程中将重叠子问题剪枝。

1. 当首次计算 𝑑𝑝[𝑖] 时，我们将其记录至 mem[i] ，以便之后使用。
2. 当再次需要计算 𝑑𝑝[𝑖] 时，我们便可直接从 mem[i] 中获取结果，从而避免重复计算该子问题。

/* 记忆化搜索 */
int dfs(int i, vector<int> &mem) {
	// 已知 dp[1] 和 dp[2] ，返回之
	if (i == 1 || i == 2)
		return i;
	// 若存在记录 dp[i] ，则直接返回之
	if (mem[i] != -1)
		return mem[i];
	// dp[i] = dp[i-1] + dp[i-2]
	int count = dfs(i - 1, mem) + dfs(i - 2, mem);
	// 记录 dp[i]
	mem[i] = count;
	return count;
}
/* 爬楼梯：记忆化搜索 */
int climbingStairsDFSMem(int n) {
	// mem[i] 记录爬到第 i 阶的方案总数，-1 代表无记录
	vector<int> mem(n + 1, -1);
	return dfs(n, mem);
}

经过记忆化处理后，所有重叠子问题都只需被计算一次，时间复杂度被优化至 𝑂(𝑛)

动态规划

记忆化搜索是一种“从顶至底”的方法：我们从原问题（根节点）开始，递归地将较大子问题分解为较小子问题，直至解已知的最小子问题（叶节点）。之后，通过回溯将子问题的解逐层收集，构建出原问题的解。
与之相反，动态规划是一种“从底至顶”的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。

int climbingStairsDP(int n) {
	if (n == 1 || n == 2)
	return n;
	// 初始化 dp 表，用于存储子问题的解
	vector<int> dp(n + 1);
	// 初始状态：预设最小子问题的解
	dp[1] = 1; //边界
	dp[2] = 2; //边界
	// 状态转移：从较小子问题逐步求解较大子问题
	for (int i = 3; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2]; //最优子结构
	}
	return dp[n];
}