[数据结构与算法]数字三角形问题（深度优先搜索 与 记忆化搜索）

题目描述

贪心算法显然不成立（局部）

用数组递推的方法

#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;
}

深度优先搜索来考虑问题（牵扯递归）
通过深度优搜索（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){//c用来记录累加的结果
	if(x==n-1){
		if(c>ans) ans=c;//去最后累加结果的最大值用ans来存储
		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;
 }

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

#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];
	else
	f[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;
 } 

记忆化搜索 即 搜索+动态规划数组记录上一层计算结果，避免过多的重复计算，算法上依然是搜索的流程，但是搜索到的一些解用动态规划的那种思想和模式作一些保存；一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。
记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。
这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。可以归纳为：记忆化搜索=搜索的形式+动态规划的思想