triangle = [
    [7],
    [3, 8],
    [8, 1, 0],
    [2, 7, 4, 4],
    [4, 5, 2, 6, 5]
]
 
def minimum_total(triangle):
    n = len(triangle)
    dp = [[0] * i for i in range(1, n + 1)]
    dp[0][0] = triangle[0][0]
 
    for i in range(1, n):
        for j in range(len(triangle[i])):
            if j == 0:
                dp[i][j] = dp[i - 1][j] + triangle[i][j]
            elif j == len(triangle[i]) - 1:
                dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]
            else:
                dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
 
    return min(dp[-1])
 
result = minimum_total(triangle)
print(result)
 
 

dHJpYW5nbGUgPSBbCiAgICBbN10sCiAgICBbMywgOF0sCiAgICBbOCwgMSwgMF0sCiAgICBbMiwgNywgNCwgNF0sCiAgICBbNCwgNSwgMiwgNiwgNV0KXQoKZGVmIG1pbmltdW1fdG90YWwodHJpYW5nbGUpOgogICAgbiA9IGxlbih0cmlhbmdsZSkKICAgIGRwID0gW1swXSAqIGkgZm9yIGkgaW4gcmFuZ2UoMSwgbiArIDEpXQogICAgZHBbMF1bMF0gPSB0cmlhbmdsZVswXVswXQoKICAgIGZvciBpIGluIHJhbmdlKDEsIG4pOgogICAgICAgIGZvciBqIGluIHJhbmdlKGxlbih0cmlhbmdsZVtpXSkpOgogICAgICAgICAgICBpZiBqID09IDA6CiAgICAgICAgICAgICAgICBkcFtpXVtqXSA9IGRwW2kgLSAxXVtqXSArIHRyaWFuZ2xlW2ldW2pdCiAgICAgICAgICAgIGVsaWYgaiA9PSBsZW4odHJpYW5nbGVbaV0pIC0gMToKICAgICAgICAgICAgICAgIGRwW2ldW2pdID0gZHBbaSAtIDFdW2ogLSAxXSArIHRyaWFuZ2xlW2ldW2pdCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICBkcFtpXVtqXSA9IG1pbihkcFtpIC0gMV1baiAtIDFdLCBkcFtpIC0gMV1bal0pICsgdHJpYW5nbGVbaV1bal0KCiAgICByZXR1cm4gbWluKGRwWy0xXSkKCnJlc3VsdCA9IG1pbmltdW1fdG90YWwodHJpYW5nbGUpCnByaW50KHJlc3VsdCkKCg==