: 三角形最佳路径问题

解题思路:三角形最佳路径经典DP， f[i][j]表示到达i行j列的最佳路径

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e2 + 10;
int g[N][N],f[N][N]; 
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= i; j ++)
			cin >> g[i][j];
	for(int i = 1; i <= n; i ++) f[i][1] = f[i-1][1] + g[i][1];
	for(int i = 2; i <= n; i ++)
		for(int j = 2; j <= n; j ++){
			f[i][j] = max(f[i-1][j],f[i-1][j-1]) + g[i][j];
		}
	int res = 0;
	for(int i = 1; i <= n; i ++) if(res < f[n][i]) res = f[n][i];
	cout << res;
	return 0;
}