浅谈记忆化搜索_alaso_shuang的博客-爱代码爱编程

记忆化搜索是什么？

就是咱找过的东西不需要再花时间去找，节约了人力和时间不是吗？

（像激素调节一样，高效！！！！）

咱拿个例子来说：数字金字塔

这是经过整理以后的数据

 这种是通过递归画出它的搜索树，很直观对吧，那由此我们可以写出（看图可以得知上一次的答案 + 当前需要加上的数（左子树） = 右子树的数）

但是这种写法肯定会超时，因为额、每一条路径都重复搜索了！！！ 

//c表示记录从上到下的累加和

void dfs(int x,int y,int c)
{
    if(x == n-1)
    {
    if(c > ans)ans = c;
    return;
}
   dfs(x+1,y,c + a[x+1][y]);
   dfs(x+1,y+1,c+a[x+1][y+1]);
}

所以我们改造为下列这个图 

void dfs(int x,int y)
{
    if(f[x][y] != 0) return f[x][y];//记忆化搜索，如果有数被搜到了，那就直接取出来累加即可
    if(x == n-1)
    f[x][y] = a[x][y];
    else 
    f[x][y] = a[x][y] + max(dfs(x+1,y),dfs(x+1,y+1));//加完左子树再去回溯到右子树那边进行累加
    return f[x][y];
}

 其实类似于从下到上，逆向思维做这题