piramide.cpp

//Piramide - Fase 1 P1 - 2018
//Por Lucio Cardoso
//Complexidade: O(n²)

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 110;

int num[MAXN][MAXN], soma[MAXN][MAXN], dp[MAXN][MAXN], n;

// pre-cálculo em O(n^2) para encontrar soma[][]
void pre(void)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            soma[i][j] = soma[i][j-1]+num[i][j];
}

// recursão em O(n^2)
int f(int k, int j)
{
    if (k == 1) return num[1][j]; // caso base
    if (dp[k][j] != -1) return dp[k][j]; // se f(k,j) já foi calculado

    int s = soma[k][j+k-1]-soma[k][j-1]; // soma na linha atual
    int caso1 = f(k-1, j);
    int caso2 = f(k-1, j+1);

    // salvo em dp a resposta de f(k, j) e a retorno
    return dp[k][j] = s+min(caso1, caso2);
}

int main(void)
{
    cin >> n;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> num[i][j];
    pre(); // faço o pré-cálculo

    // inicializo dp com um valor que nunca será resposta, digamos -1
    memset(dp, -1, sizeof dp);
    cout << f(n, 1) << "\n"; // imprimo a resposta, começando na base
}