当前位置：首页 > article >正文

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

article 2025/3/7 3:53:25

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

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;
}