记忆化搜索与动态规划：原理、实现与比较

        记忆化搜索和动态规划是解决优化问题的两种重要方法，尤其在处理具有重叠子问题和最优子结构性质的问题时非常有效。

目录

1. 记忆化搜索（Memoization）

定义：

实现步骤：

示例代码（斐波那契数列）：

2. 动态规划（Dynamic Programming）

定义：

实现步骤：

示例代码（斐波那契数列）：

3. 不同点与相同点

不同点：

相同点：

4. 联系与本质

联系：

本质：

5. 总结

---

1. 记忆化搜索（Memoization）

定义：

记忆化搜索是一种优化递归算法的方法，通过存储已经计算过的子问题的结果，避免重复计算。

实现步骤：

1. 添加备忘录：通常使用数组或哈希表来存储已经计算过的结果。

2. 递归返回时存储结果：在每次递归调用返回时，将结果存储在备忘录中。

3. 递归前检查备忘录：在每次递归调用前，检查备忘录中是否已经有结果，如果有则直接返回。

示例代码（斐波那契数列）：

#include <iostream>
#include <vector>
using namespace std;int fib(int n, vector<int>& memo) {if (n <= 1) return n;if (memo[n] != -1) return memo[n];memo[n] = fib(n-1, memo) + fib(n-2, memo);return memo[n];
}int main() {int n = 10;vector<int> memo(n+1, -1);cout << "Fibonacci number is " << fib(n, memo) << endl;return 0;
}

2. 动态规划（Dynamic Programming）

定义：

动态规划是一种将复杂问题分解为更简单的子问题的方法，通过填表的方式自底向上解决问题。

实现步骤：

1. 确定状态表示：定义状态变量，如dp[i]表示第i个斐波那契数。

2. 推导状态转移方程：如dp[i] = dp[i-1] + dp[i-2]。

3. 初始化：设置初始条件，如dp[0] = 0, dp[1] = 1。

4. 确定填表顺序：通常从左到右填写。

5. 确定返回值：返回所需的结果，如dp[n]。

示例代码（斐波那契数列）：

#include <iostream>
#include <vector>
using namespace std;int fib(int n) {if (n <= 1) return n;vector<int> dp(n+1);dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; ++i) {dp[i] = dp[i-1] + dp[i-2];}return dp[n];
}int main() {int n = 10;cout << "Fibonacci number is " << fib(n) << endl;return 0;
}

3. 不同点与相同点

不同点：

• 实现方式：记忆化搜索是自顶向下的递归方法，而动态规划是自底向上的递推方法。

• 存储方式：记忆化搜索使用备忘录存储中间结果，动态规划使用表格存储状态。

• 调用顺序：记忆化搜索依赖于递归调用，动态规划依赖于循环迭代。

相同点：

• 优化目标：两者都旨在避免重复计算，提高算法效率。

• 适用问题：都适用于具有重叠子问题和最优子结构性质的问题。

4. 联系与本质

联系：

• 本质相同：两者都是对暴力解法的优化，通过存储中间结果来避免重复计算。

• 相互转化：记忆化搜索可以看作是动态规划的递归实现，动态规划可以看作是记忆化搜索的迭代实现。

本质：

• 暴力解法优化：两者都是对暴力解法的优化，通过存储已经计算过的值来减少计算量。

• 重叠子问题：都利用了问题的重叠子问题性质，通过存储和重用子问题的解来提高效率。

5. 总结

        记忆化搜索和动态规划在本质上是相似的，都是通过存储中间结果来优化暴力解法。它们的主要区别在于实现方式和调用顺序。在实际应用中，选择哪种方法取决于具体问题的性质和编程习惯。理解它们的异同和联系，有助于更好地应用这些方法解决复杂的优化问题。