动态规划+深度优先搜索+记忆化搜索（干货满满）

动态规划的定义

动态规划算法与分治法的思想类似，都是通过组合子问题的解来求原问题。我先来给大家介绍一下分治思想，分治思想就是把一个复杂的问题，分解为k个规模相同的子问题，如果还是无法解决，子问题又可以分为若干个相同规模的子问题求解，之后组合求原问题（难点）如二分法，归并排序，折半查找。至于动态规划：就是一个最优化问题，先将问题分解为子问题，并且对于这些分解的子问题自身就是最优的才能在这个基础上得出我们要解决的问题的最优方案（假设最优然后去求），要不然的话就能找到一个更优的解来替代这个解，得出新的最优自问题，这当然是和前提是矛盾的。同于 贪心算法，因为贪心算法是从局部最优来解决问题，而动态规划是全局最优的。用动态规划的时候不可能在子问题还没有得到最优解的情况下就做出决策，而是必须等待子问题得到了最优解之后才对当下的情况做出决策，所以往往动态规划都可以用 一个或多个递归式来描述。而贪心算法却是先做出一个决策，然后在去解决子问题。这就是贪心和动态规划的不同。

–摘自剑锋OI博文

动态规划求解问题的三个基本条件

1）无后效性： 动态规划要求已经求解的子问题不受后续阶段的影响，以保证对每一阶段的计算能够按顺序、不重复地执行。

2）最优子结构性质： 在动态规划算法求解问题的过程中，下一阶段的解应该能由前面各阶段子问题的最优解导出。

3）子问题重叠性： 动态规划所针对的问题还有另外一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复，称为子问题重叠性质。用动态规划求解问题的一般思路

1）首先要确定子问题的状态，这是一个关键（即确定dp数组代表的含义是什么）。

2）确定状态转移方程（可用于计算各阶段同类子问题的计算公式）进而求解原问题。

动态规划和贪心类似，都没有固定的解题模板，只能通过多刷题，多分析来确定问题的状态转移方程(重点)，进而求解问题。

下面我们通过做一些题目来进一步理解动态规划。

最长上升子序列问题

题目出自SDUTOJ

题解：

我们要求最长上升子序列的长度，自然要挨个数字来寻找，这时我们用dp[i]来表示用i个数字结尾的最长上升子序列的长度。

样例 1 7 3 5 9 4 8

dp[i] 1 2 2 3 3 …

dp[2]：

dp[2]=dp[1]+1;

dp[3]:

dp[3]=dp[1]+1;

dp[4]:

dp[4]=dp[1]+1;

dp[4]=dp[3]+1;

这时我们发现了什么规律呢？

没错从第一位数字开始寻找，找到一个比当前的数小的数就+1更新一下，直到遍历到当前数字。

我们就得到状态转移方程

dp[i]=max( dp[j] + 1, dp[i] ) 0<j<i;

#include <iostream>using namespace std;const int N=1000;int a[N],dp[N];int main(){int n;int res=0;cin>> n;dp[0]=0;a[0]=-1; //注意这里为什么要让a[0]=-1?还是说让a[0]小于某个数就行？ 继续往下看for(int i=1;i<=n;i++){cin>>a[i];for(int j=0;j<i;j++){if(a[j]<a[i]){//这里我们第一次发现了a数组的比较 j从0开始也就发现了上面关于a[0]的问题//我们注意到a[i]任意一个数是大于等于0的而a[0]是负数 结合下面的代码我们发现其目的就是在于解决最小上升子序列的长度为1的情况dp[i]=max(dp[i],dp[j]+1);}}res=max(res,dp[i]);}cout<<res<<endl;return 0;}

shi最长公共子序列问题（LCS问题）

题目源自SDUTOJ

题解：

状态表示：我们用dp[i][j]表示数字A[1,i]与B[1,j] 的最长公共子序列长度。

分析：

当s1[i]=s2[j]时 dp[i][j]=d[i-1][j-1]+1; 因为相同时肯定是最长公共子序列长度+1；

当s1[i]!=s2[j]时 dp[i][j]=max(dp[i][j-1],dp[i-1][j]) 举个例子：

ABC A

ABD C

可得dp[4][4]=dp[3][4];

#include <iostream>#include <string.h>using namespace std;const int N=505;int dp[N][N];char s1[N],s2[N];int main(){int n,m;while(~scanf("%s %s",s1+1,s2+1)){n=strlen(s1+1);m=strlen(s2+1); //数组统一往后移动一位是考虑到边界问题for(int i=0;i<n;i++) dp[i][0]=0;for(int j=0;j<m;j++) dp[0][j]=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s1[i]==s2[j]) {dp[i][j]=dp[i-1][j-1]+1;}else {dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}}printf("%d\n",dp[n][m]);}return 0;}

有一点小问题：有一些人认为不用考虑s1[i]==s2[j]的这种情况，因为dp[i-1][j]=dp[i-2][j]+dp[i-1][j-1] 也就是说else后面的这一种情况全部都可以包括，但我不这么认为，原因如下：如果只有else后面的语句得出的结果是0，我们建立表格时发现整个表格全部为零，我结合if里的语句简单的分析了一下，else语句的dp数组建立的表格确实能包括dp[i][j]但是从问题的角度来分析，s1[i]=s2[j]这种情况并没有被包括，就和贪心一样指一种情况对结果有一定的贡献所以不能舍弃（一点小的见解，仅供参考）

数字三角形问题–深度优先搜索–记忆化搜索

首先，我们来看一个用数组递推的方法求的代码：

#include <algorithm>#include <bitset>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <functional>#include <iostream>#include <map>#include <queue>#include <set>#include <stack>#include <string>#include <vector>using namespace std;const int N=111;int dp[N][N],a[N][N];int main(int argc, char const *argv[]) {int n;int res=0;int i,j;cin>>n;for(i=1;i<=n;i++){for(j=1;j<=i;j++){cin>>a[i][j];}}dp[1][1]=a[1][1];for( i=2;i<=n;i++){dp[i][1]=dp[i-1][1]+a[i][1];dp[i][i]=dp[i -1][i- 1] +a[i][i]; //边界情况for(j=2;j<i;j++){dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]; }}for(int i=1;i<=n;i++) res=max(res,dp[n][i]); //求各个路径结果的最大值cout<<res;return 0;}

然后使用深度优先搜索来考虑问题（牵扯递归）

void dfs(x,y,c){//c用来记录累加的结果if(x==n-1){if(c>ans) ans=c //取最后累加结果的最大值 ans用来存储return ;} dfs(x+1,y,c+a[x+1][y]);dfs(x+1,y+1,c+a[x+1][y+1]);}

通过深度优搜索（dfs）画出递归树来模拟执行过程

代码如下：

#include <iostream> //超时算法using namespace std;const int N=1e5+10;int a[N][N];int ans=0;void dfs(int x,int y,int c,int n){if(x==n-1){if(c>ans) ans=c;return ;}dfs(x+1,y,c+a[x+1][y],n);dfs(x+1,y+1,c+a[x+1][y+1],n);}int main(){int n;cin>>n;for(int i=0;i<n;i++){for(int j=0;j<=i;j++){cin>>a[i][j];}} dfs(0,0,a[0][0],n);cout<<ans<<endl;return 0;}

深度优先搜索其实质就是二叉树的先序遍历（没学过的直接用递推或者递归的算法求解）

我们发现有些点被重复搜索了好几遍这就耗费了很多的时间，实际上也是这样的这种算法的时间复杂度为O(2^n)指数级复杂度肯定要超时的，这时我们就希望有一种算法能够在第一次搜索的过程中就记录下来之后用的时候就不需要继续搜索了，这就引出我们的记忆化搜索。

记忆化搜索

我们发现从上向下累加和是不能重复的，但从下向下的累加是可以重复用的这也是记忆化搜索的前提。记忆化搜索：对递归树做了剪枝，搜索过的子树不再重复搜索，直接返回储存值。下面来看代码：

#include <iostream>using namespace std;const int N=1500;int a[N][N];int f[N][N]; //记录从上到下的累加和 int ans=0;int n;int dfs(int x,int y){//记忆搜索， 避免进一步递归 if(f[x][y]!=0) return f[x][y]; //由于开全局数组初始化都为0不为零就相当于已经搜索过就记录下来 if(x==n-1) //边界条件 f[x][y]=a[x][y];elsef[x][y]=a[x][y]+max(dfs(x+1,y),dfs(x+1,y+1));return f[x][y];}int main(){cin>>n;for(int i=0;i<n;i++){for(int j=0;j<=i;j++){cin>>a[i][j];}} dfs(0,0);cout<<f[0][0]<<endl;return 0;}

我对动态规划的理解

其实找准动态规划与贪心的区别后，理解起来就不那么难了，动态规划的关键词就是状态和状态转移方程，找好这两个问题就可以解决了，然后dfs深搜，和记搜有时候牵扯到后面的二叉树，先不用理解的太深，代码就多一行记住后以后就会慢慢的理解了。其实递推的方法求数塔问题是也是有用数组记录了值，和记忆化搜索有些相似，大家可以结合理解，加油！