记忆化搜索

是什么：带备忘录的递归 如何实现？ 1.添加一个备忘录 <可变参数，返回值> 2.递归每次返回的时候，将结果放到备忘录里 3.在每次进入递归的时候，往备忘录里看看

例

斐波那契：斐波那契 记忆化搜索代码：

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==1)
    {
        memo[n]=n;  //返回前，将结果放入备忘录
        return n;
    }

    memo[n]=dfs(n-1)+dfs(n-2);
    return memo[n];
}

动态规划

动态规划斐波那契代码:

int fib(int n)
{
    int dp[31];
    dp[0]=0,dp[1]=1;  //初始化
    for(int i=2;i<=n;i++)
    {
        dp[i]=dp[i-1]+dp[i-2];  //递推(状态转移方程)
    }
    return dp[n];
 }

记忆化搜索与动态规划

都是一回事 只不过记忆化搜索是递归的形式 而常规的动态规划是递推（循环）的形式 很多时候可以这样： 暴搜->记忆化搜索->动态规划