1、B站视频链接：E01 记忆化搜索 数字三角形_哔哩哔哩_bilibili

题目要求：求累加的最大值

#include <bits/stdc++.h>
using namespace std;
int n=4;
int a[9][9]={{1},
			 {4,6},
			 {8,3,9},
			 {5,7,2,1}};//搜索树
int f[9][9];//记录从下向上的累加和
int dfs(int x,int y){
	if(f[x][y]!=0)return f[x][y];//记忆化搜索，剪枝
	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(){
	dfs(0,0);
	printf("max=%d\n",f[0][0]);
	return 0;
} 

2、B站视频链接：E02 线性DP 数字三角形_哔哩哔哩_bilibili

数塔逆推

#include <bits/stdc++.h>
using namespace std;
int n=4;
int a[9][9]={{1},
			 {4,6},
			 {8,3,9},
			 {5,7,2,1}};//搜索树
int b[9][9];//用于备份
int p[9][9];//记录路径
int main(){
	int x,y;
	//备份数据，起点为(0,0)
	for(x=0;x<n;x++){
		for(y=0;y<=x;y++){
			b[x][y]=a[x][y];
		}
	} 
	//向上逐层累加
	for(x=n-2;x>=0;x--){//从下往上 
		for(y=0;y<=x;y++){//从左往右 
			if(a[x+1][y]>a[x+1][y+1]){//下与右下的比较
				a[x][y]+=a[x+1][y];
				p[x][y]=0;//向下,列数/列坐标不变 
			}else{
				a[x][y]+=a[x+1][y+1];
				p[x][y]=1;//向右下 ，列数/列坐标加一 
			} 
		}
	} 
	cout<<"max="<<a[0][0]<<endl;
	//输出数塔最大值的路径
	for(x=0,y=0;x<n-1;x++){
		cout<<b[x][y]<<"->";
		y+=p[x][y];//下一行的列数 
	} 
	cout<<b[n-1][y]<<endl;
	return 0;
}