题意

输入一个数字金字塔，每个点有一个数。从最上面的点走到最底层，求经过路程的最大值

PS：是走到最底层随便一个点哦

思路

正向求

第 $i_j$ 个点可以从左上和上面走下来，所以第 $i_j$ 等于左上和上面中的最大值

反向求

第 $i_j$ 个点可以从下面和右下走上来，所以第 $i_j$ 要加下面和右下中的最大值

代码（正向求）

#include <bits/stdc++.h>
using namespace std;
int a[1005][1005],mx;
int main(int argc, char **argv){
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++){
		for (int j = 1;j <= i;j++){
			int x;
			cin >> x;
			a[i][j] = max(a[i - 1][j - 1],a[i - 1][j]) + x;	// 左上的数和上面的数取最大值，然后加上本格的数
		}
	}
	for (int i = 1;i <= n;i++){
		mx = max(mx,a[n][i]);	// 找最后一行最大的数
	}
	cout << mx;
	return 0;
}

代码（反向求）

#include <bits/stdc++.h>
using namespace std;
int a[1005][1005],mx;
int main(int argc, char **argv){
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++){
		for (int j = 1;j <= i;j++){
			cin >> a[i][j];
		}
	}
	for (int i = n - 1;i > 0;i--){	// 下到上
		for (int j = 1;j <= i;j++){	// 左到右
			a[i][j] += max(a[i + 1][j],a[i + 1][j + 1]);	// 加 下面和右下 对比更大的那个
		}
	}
	cout << a[1][1];
	return 0;
}

$update 2024/3/18:$ 更新了反向求的代码

题意

求金字塔顶部到底部最长路径和

思路

分两种

• 正向求和(递归)
  • 特殊情况返回的条件
    • 没有路时
    • 底部时
  • 返回
    • 返回下面两个的最大值
• 反向求和(递推)
  • 从底部往上递推
    • 数组设置为下面两个的最大值

代码(正向求和)

#include<iostream>
using namespace std;
int a[114][514],b[114][514],n;
int f(int x,int y)
{
	if(b[x][y]!=0)//没有路时
	{
		return b[x][y];//返回
	}
	if(x==n)//底部时
	{
		return b[x][y]=a[x][y];//返回
	}
	b[x][y]=a[x][y]+max(f(x+1,y),f(x+1,y+1));//获取下面两个的最大值
	return b[x][y];//返回
}
int main()
{
	cin>>n;//输入
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<i+1;j++)
		{
			cin>>a[i][j];//输入
		}
	}
	cout<<f(0,0);//输出
	return 0;//完结散花
}

代码(反向求和)

#include<iostream>
using namespace std;
int n,a[1145][1145];
int main()
{
	cin>>n;//输入
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<i+1;j++)
		{
			cin>>a[i][j];//输入
		}
	}
	for(int i=n-2;i>=0;i--)//复杂的范围
	{
		for(int j=0;j<=i;j++)//复杂的范围
		{
			a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
		}
	}
	cout<<a[0][0];//输出下面两个的最大值
	return 0;//完结散花
}

#include<bits/stdc++.h>
using namespace std;
int a[1005][1005],vst[1005][1005];//a来存金字塔，vst来搞记忆递归 
int r;
//开始dfs 
int dfs(int x,int y){
	if(vst[x][y]!=-1) return vst[x][y];
	//若有存这个答案就直接返回 
	if(x==r) return vst[x][y]=a[x][y];
	//搜索到底了就返回并存下计算结果 
	return vst[x][y]=a[x][y]+max(dfs(x+1,y),dfs(x+1,y+1));
	//否则继续递归找答案 
}
int main(){
	cin>>r;
	memset(vst,-1,sizeof(vst));//memset赋值-1 
	for(int i=0;i<r;i++) for(int j=0;j<=i;j++) cin>>a[i][j];
	cout<<dfs(0,0)<<"\n";//从（0,0）开始搜 
	return 0;
}

题意

计算三角形的最大路径

死路

非常简单，一个a保存数，一个f保存状态，简单的DP

装态转义放秤

AC没问题歹马

#include<iostream>
using namespace std;
int main(){
	int r;
	cin>>r;
	int a[r][r];
	for(int i=0;i<r;i++)
		for(int j=0;j<=i;j++)
			cin>>a[i][j];
	int f[r][r]={};
	for(int i=0;i<r;i++)
		for(int j=0;j<=i;j++)
			if(i-1<0)
				f[i][j]=a[i][j];
			else
				if(j-1<0)
					f[i][j]=f[i-1][j]+a[i][j];
				else
					f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
	int ans=0;
	for(int i=0;i<r;i++)
		ans=max(ans,a[r-1][i]);
	cout<<ans;
}

思路

可以不用a数组，直接存到f数组，反正也不用使用那些被覆盖得了。

状态转移方程

代码

#include<iostream>
using namespace std;
int main(){
	int r;
	cin>>r;
	int f[r][r]={};
	for(int i=0;i<r;i++)
		for(int j=0;j<=i;j++)
			cin>>f[i][j];
	for(int i=1;i<r;i++)//i=1就直接等于了原来
		for(int j=0;j<=i;j++)
			if(j-1<0)
				f[i][j]+=f[i-1][j];
			else
				f[i][j]+=max(f[i-1][j-1],f[i-1][j]);
	int ans=0;
	for(int i=0;i<r;i++)
		ans=max(ans,f[r-1][i]);
	cout<<ans;
}