记忆化搜索和动态规划是解决优化问题的两种重要方法，尤其在处理具有重叠子问题和最优子结构性质的问题时非常有效。
目录
1. 记忆化搜索（Memoization）
定义：
实现步骤：
示例代码（斐波那契数列）：
2. 动态规划（Dynamic Programming）
定义：
实现步骤：
示例代码（斐波那契数列）：
3. 不同点与相同点
不同点：
相同点：
4. 联系与本质
联系：
本质：
5. 总结
1. 记忆化搜索（Memoization）
定义：
记忆化搜索是一种优化递归算法的方法，通过存储已经计算过的子问题的结果，避免重复计算。
实现步骤：
-
添加备忘录：通常使用数组或哈希表来存储已经计算过的结果。
-
递归返回时存储结果：在每次递归调用返回时，将结果存储在备忘录中。
-
递归前检查备忘录：在每次递归调用前，检查备忘录中是否已经有结果，如果有则直接返回。
示例代码（斐波那契数列）：
#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）
定义：
动态规划是一种将复杂问题分解为更简单的子问题的方法，通过填表的方式自底向上解决问题。
实现步骤：
-
确定状态表示：定义状态变量，如
dp[i]表示第i个斐波那契数。 -
推导状态转移方程：如
dp[i] = dp[i-1] + dp[i-2]。 -
初始化：设置初始条件，如
dp[0] = 0, dp[1] = 1。 -
确定填表顺序：通常从左到右填写。
-
确定返回值：返回所需的结果，如
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. 总结
记忆化搜索和动态规划在本质上是相似的，都是通过存储中间结果来优化暴力解法。它们的主要区别在于实现方式和调用顺序。在实际应用中，选择哪种方法取决于具体问题的性质和编程习惯。理解它们的异同和联系，有助于更好地应用这些方法解决复杂的优化问题。
