预备:这道题其实一上来我们就想到,每次选最大的走,但局部最优并不一定能得到全局最优. 两个方向,即两种选择. (x,y)-->(x+1,y+1)斜着走; (x,y)-->(x+1,y)竖着走 注意这里的x,y不是指数学中坐标,而是第i行第j个数,即二维数组中的i,j; 何为dfs? dfs即递归 难点1：在递归中调用递归如何理解？ 在最后一步结束之前,dfs的值一直是虚空的,但是有的,但只有直到算到最优,才定下来;还有一层意思就是你算了这个数,但你没存下这个数,你无法直接查询某个dfs的值,除非你枚举输出所有dfs的值 难点2：从什么位置开始搜？ 从(1,1)吗?如果这样那我们到达最后一行后,无法接着向下,但我们可能还可以向右,无法确定递归出口,这时候又需要一个for循环 dfs(n,i),扫到最大.不妨从底到(1,1) 递归出口确定为(1,1),就简单很多 难点3：如何输出最优轨迹呢 还是从底到(1,1),一个点可以转移到各个位置,如果直接输出,得到是整个dfs的过程点,而我们需要最优的,那么我们只要先保证当前点为最优点,然后向上找上一个最优点,这就和dfs想法一样,虚空出所有可能,但只有当结果最优时确定输出,显然这也要用到递归.那我们怎么知道他是最优的呢?我们可以在dfs时处理,如果dfs最优,进行标记,使用bool数组 0是如何移动 1是如何移动(两个选择) 从而确定整个轨迹坐标 1.dfs(t了六个点)

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+9;
int mp[N][N];
int n;
bool to[N][N]={0};

//要么竖着走，要和斜着走
int dfs(int x,int y)
{
	
	if(x>n || y>n)return 0;
	else
	{             
		if(dfs(x+1,y)>dfs(x+1,y+1))
		{
			to[x][y]=1;
		}
		else
		{
			to[x][y]=0;
		}
		return max(dfs(x+1,y),dfs(x+1,y+1))+mp[x][y];
	}             //竖着       //斜着  
}

void path(int x,int y)
{
	if(x>n)return;
	cout<<x<<' '<<y<<'\n';
	if(to[x][y])
	{
		path(x+1,y);
	}
	else path(x+1,y+1);
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=i;++j)cin>>mp[i][j];
	}
	int res=dfs(1,1);
    path(1,1);
	cout<<res;
	return 0;
}

2.刚才我们说到dfs的结果是虚空的,而我们直接暴力地去搜,显然我们会有许多重复运算,于是我们想到用一个数组来存每次dfs得到的值,即方法二:记忆化搜索

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+9;
int mp[N][N];
int mem[N][N];
int n;
bool to[N][N]={0};

//要么竖着走，要和斜着走
int dfs(int x,int y)
{
	if(mem[x][y])return mem[x][y];
	int sum=0;
	if(x>n || y>n)sum=0;
	else
	{             
		if(dfs(x+1,y)>dfs(x+1,y+1))
		{
			to[x][y]=1;
		}
		else
		{
			to[x][y]=0;
		}
		sum=max(dfs(x+1,y),dfs(x+1,y+1))+mp[x][y];
	}             //竖着       //斜着 
	mem[x][y]=sum;
	return sum; 
}

void path(int x,int y)
{
	if(x>n)return;
	cout<<x<<' '<<y<<'\n';
	if(to[x][y])
	{
		path(x+1,y);
	}
	else path(x+1,y+1);
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=i;++j)cin>>mp[i][j];
	}
	dfs(1,1);
    path(1,1);
	cout<<mem[1][1];
	return 0;
}

3.当我们写出dfs的时候,很自然的就会想到这道题 dp的做法。我们将复杂的dfs过程缩减成一个状态转移方程。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+9;
int mp[N][N];
int n;
bool to[N][N]={0};
int f[N][N];

void path(int x,int y)
{
	if(x>n)return;
	cout<<x<<' '<<y<<'\n';
	if(to[x][y])
	{
		path(x+1,y);
	}
	else path(x+1,y+1);
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=i;++j)cin>>mp[i][j];
	}
	
	for(int i=n;i>=1;--i)
	{
		for(int j=1;j<=n;++j)
		{
			if(f[i+1][j]>f[i+1][j+1])
			{
				to[i][j]=true;
			}
			else to[i][j]=false;
			
			f[i][j]=max(f[i+1][j],f[i+1][j+1])+mp[i][j];
		}
	}
	
    path(1,1);
	cout<<f[1][1];
	return 0;
}

4.前不久 迪杰斯特拉算法被证明普遍最优,加上dp思想的启发(官方题解)

#include<iostream>
using namespace std;
const int N=1e3+9;
int mp[N][N];
bool to[N][N]={0};
int n;

void path(int x,int y)
{
	if(x>n)return;
	cout<<x<<' '<<y<<'\n';
	if(to[x][y])path(x+1,y);
	else path(x+1,y+1);
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=i;++j)cin>>mp[i][j];
	}
	
	for(int i=n;i>=1;--i)
	{
		for(int j=1;j<=n;++j)
		{
			if(mp[i+1][j]>mp[i+1][j+1])
			{
				to[i][j]=true;
				mp[i][j]+=mp[i+1][j];
			}
			else
			{
				to[i][j]=false;
				mp[i][j]+=mp[i+1][j+1];
			}
		}
	}
	
	path(1,1);
	cout<<mp[1][1];
	return 0;
}