洛谷P1216-数字三角形-题解

写题解是个好习惯，也不失为一个充实博客的好办法😏。

题目链接：https://www.luogu.com.cn/problem/P1216
针对这一题，我们可以使用记忆化搜索的方式去做。

#include <bits/stdc++.h>//万能头文件
using namespace std;
int r;//行数
int dp[1005][1005];//实现记忆化搜索的数组
int inp[1005][1005];//存放输入数据的数组
int dfs(int x,int y) {
	if(dp[x][y]!=-1) return dp[x][y];//如果已经求过，直接调用dp数组
	if(x==r-1) return dp[x][y]=inp[x][y];//如果到了最后一层，返回总和
	return dp[x][y]=inp[x][y]+max(dfs(x+1,y),dfs(x+1,y+1));//一般情况，计算出到目前为止走过的数字的和，并保存到dp数组
}
int main() {
	cin>>r;
	for(int i=0; i<r; i++) {
		for(int j=0; j<=i; j++) {
			cin>>inp[i][j];//输入
			dp[i][j]=-1;//将dp数组初始化为-1
		}
	}
	cout<<dfs(0,0);
	return 0;
}