[数据结构与算法]动态规划之递推和记忆化搜索

类似于递归的一种DP方法，称之为递推+记忆化搜索。避免由DP转化为递归之后的重复运算就是记忆化搜索。
一道例题来理解

给定一个等边三角形图案由n行m列构成，第n行元素有n个，从第一行走到最后一行，每次只能走左下右下两个节点，每个节点有自己的数值当走到这个节点时获得这个节点的数值，问走哪个路径能让我最后的数值最大。

排列组合原理的话，路径数是：22222******2=pow(2,n)个，这遍历起来不得个千把个年头。

现有n平方级算法如下

#include <iostream>

using namespace std;

int main()
{
    int n,a[150][150],dp[150][150];
   for(int i=1;i<=n;i++)
   /*输入数值*/
   {
       for(int j=1;j<=i;j++)
       {
           cin>>a[i][j];
       }
   }
   for(int i=0;i<n;i++)
   /*预处理第一行，对比递归过程中的“基础值”进行理解*/
   {
       dp[n][i]=a[n][i];
   }
   /*开始递推+记忆化搜索*/
   for(int i=n-1;i>=1;i--)
   {
       for(int j=1;j<=i;j++)
       {
           dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1])/*每次的最大值就是目前这个节点值+从底层走到这一层的最大值节点。*/
       }
   }
    return 0;
}

我们发现如果用递归的：基础值+递推关系+最终状态=最终求解
我们就可以用一个递归函数来写

/*初始从第一个元素开始*/
int DFS(int i,int j)
{
    if(i==n)
    return dp[i][j];
    else
    return dp[i][j]=max(DFS(i+1,j),DFS(i+1,j+1))+a[i][j];
    //
}

可见，未经过记忆化搜索的DP改造成的递归本身时间复杂度相当高。
为么复杂度会这么高呢，不难看出在DFS搜索所有路径的时候有相当一部分是重复运算，避免由DP转化为递归之后的重复运算就是记忆化搜索。

用递归+记忆化搜索后重写的核心部分如下
初始化dp为-1

int DFS(int i,int j)
{
   if(i==n)
   return dp[i][j];
   if(dp[i][j]>=0)/*避免重复计算，实现记忆化搜索*/
   return dp[i][j];
   return dp[i][j]=a[i][j]+max(DFS(i+1,j),DFS(i+1,j+1));
}