Türkçe

Piramitteki değerleri (odalardaki fotoğraf sayılarını) iki boyutlu bir diziye kaydederek başlayabiliriz. Daha sonra yukarıdan aşağı doğru giderek her yolu tek tek denemek yerine, en alt kattaki odalardan başlayıp, yukarı doğru optimal değerleri alarak ilerleyebiliriz. Bu şekilde her oda için, en aşağı optimal şekilde inmenin yolunu bulmuş oluruz. Örneğin en alt katın bir üstündeki bir odayı, o odanın altındaki iki odadan en büyüğünü baktığımız odaya ekleyerek hesaplayabiliriz. Bunu yukarı doğru tüm odalar için yaptığımızda, iki boyutlu dizinin 0'a 0 pozisyonu bize en üstten en alta en fazla kaç fotoğraf görerek inebileceğimizi verir.

English

We can start with putting the values in the pyramid into a 2D array. Then, instead of traversing from top to bottom with checking every single path, we can start from the rooms on the lower-most floor and move upwards with taking the optimal values. This way, we can find the optimal path to move from top to bottom. For instance, when calculating a room on the 2nd floor (the floor above the lower-most), we must look at the two rooms below and add the greater value to the room we are calculating. If we do this for every room and every floor, moving from bottom to top, the 0 to 0th index of our array will give us the optimal solution.

#include <iostream>

#define ll long long

ll arr[1000][1000];

int main(){
    ll n,m;
    std::cin>>n;
    for(int i=0;i<n;i++)
        for(int k=0;k<=i;k++)
            std::cin >> arr[i][k];

    for(int i=n-2;i>=0;i--)
        for(int k=0;k<=i;k++)
            arr[i][k] += max(arr[i+1][k], arr[i+1][k+1]);

    std::cout << arr[0][0]%1000000007<<'\n';
}