Solução

Um problema de aplicação direta de programação dinâmica.

Vamos chamar $dp_{ij}$ de melhor solução partindo da linha $i$ e coluna $j$ .

A partir disso podemos achar a recursão:

$dp_{ij} = max(dp_{i+1, j}, dp_{i+1, j+1}) + v_{ij}$

O que podemos ver nessa recurção, é que, a melhor solução partindo de um certo ponto é o valor daquele ponto, mais o valor máximo partindo de um dos pontos sob ele.

Assim computando recursivamente podemos achar a solução em $O(n^2)$ , que passa no tempo.

Código:

	#include <bits/stdc++.h>

	using namespace std;

	const int maxn = 110;

	int v[maxn][maxn];
	int dp[maxn][maxn];

	int main()
	{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) {

	for (int j = 1; j <= i; j++) cin >> v[i][j];
	}

	for (int i = 1; i <= n; i++) dp[n][i] = v[n][i];

	for (int i = n-1; i >= 1; i--) {

	for (int j = 1; j <= i; j++) {

	dp[i][j] = v[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
	}
	}

	cout << dp[1][1] << "\n";

	return 0;
	}

view raw

triangulo.cpp

hosted with ❤ by GitHub