记忆化搜索与动态规划刷题总结

记忆化搜索 vs 动态规划

1. 记忆化搜索：有完全相同的问题/数据保存起来，带有备忘录的递归
2. 记忆化搜索的步骤：
   1. 添加一个备忘录 <可变参数，返回值>
   2. 递归每次返回的时候，将结果放入备忘录中
   3. 在每次进入递归的时候，往备忘录中查找一下
3. 记忆化搜索和常规的动态规划都是动态规划，暴搜 -> 记忆化搜索 -> 动态规划
4. 有大量重复的问题才能改成记忆化搜索

斐波那契数

题目链接

题解

1. 创建一个备忘录
2. 把备忘录中的值初始化为斐波那契数中不可能出现的值 -1
3. 在每次递归完成之前，把值存入备忘录中
4. 在每次进入递归的时候，查找一下备忘录中是否有值，有值就直接返回，相当于剪枝

代码

#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

// 记忆化搜索
class Solution {
public:
    int memo[31];
    
    int fib(int n) {
        memset(memo, -1, sizeof memo);
        return dfs(n);
    }
    
    int dfs(int n) {
        if (memo[n] != -1) {
            return memo[n];
        }
        if (n == 0 || n == ) {
            memo[n] = n;
             n;
        }
        memo[n] = (n - ) + (n - );
         memo[n];
    }
};


  {
:
     dp[];
    
    {
        dp[] = , dp[] = ;
         ( i = ; i <= n; i++) {
            dp[i] = dp[i - ] + dp[i - ];
        }
         dp[n];
    }
};