def solution(triangle):
    if len(triangle) == 1:
        return triangle[0][0]

    answer = 0
    dp = [[triangle[0][0]]]

    for i in range(1, len(triangle)):
        dp.append([])

        for j in range(len(triangle[i])):
            if j == 0:
                before = dp[i - 1][j]
            elif j == i:
                before = dp[i - 1][j - 1]
            else:
                before = max(dp[i - 1][j], dp[i - 1][j - 1])

            current = before + triangle[i][j]
            answer = max(answer, current)
            dp[i].append(current)

    return answer


assert (solution([[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]) == 30)
