动态规划与记忆化搜索的异同

相同点:1.两者都需要满足一个条件，即我这一步的最优决策是可以基于上一步决策确定后的结果来求出的。 意思说我在上一步决策确定后，我做这一步决策是不会影响上一步决策的。 2.都利用了递归的思想，即在一个结果的基础上去求解下一个结果，最后求出目标解

不同点：I.动态规划：动态规划的关键在于推出一个递推方程，他的求解结果是自上而下的； eg：

 for(int i=2; i<=f; i++){
        for(int j=1; j<=v; j++){
            for(int k=1; k<j; k++)
                dp[i][j]=max(dp[i][j],dp[i-1][k]+mp[i][j]);//需要明确推出上一步和这一步之间的关系
        }
    }

可以看到，我们的思路是用上一个最优解来维护下一个最优解，思路是一个顺着的思路

II.记忆化搜索：其实把记忆化搜索看做一种另类的dfs更好理解一点，我们还是跟dfs一样向下搜索 （注意这里把记忆化搜索看做一个向下的顺序，感觉上像是最底层的最优解一步一步向上回 溯，得到目标解），只是当我们搜索的值在之前已经求出时，我们就可以直接返回，不需要继续向 下递归，因为我们后面的求解是不会影响前面的步骤的（前面的步骤已经给后面的步骤设置好 了相应的限制，在这个基础上求解这种情况下这一步的最优解），这就是记忆化 。 eg：

int dfs(int fl, int bt){
   if(dp[fl][bt]!=0)
       return dp[fl][bt];
    int temp=0,ans=0;
    if(fl==f)
        return dp[fl][bt]=mp[fl][bt];
    for(int i=bt+1; i<=v-(f-fl)+1; i++){//这里已经给了条件!
       temp=dfs(fl+1,i)+mp[fl][bt];//可以看到我只关心下一步结果
        if(ans<temp){
            ans=temp;
        }
    }
    dp[fl][bt]=ans;
    return ans;
}

（学习动态规划与记忆化搜索的初印象）