动态规划代码（python

from typing import List
import copy
triangle = [
    [2],
    [3, 4],
    [6, 5, 7],
    [4, 1, 8, 3]
]
def traingle_minimum_total(traingle) -> int:
    n = len(triangle)
    dp = traingle[:]
    dp_path = copy.deepcopy(traingle)
    dp_path[0][0] = '[0, 0]'
    for row in range(1, n):
        for col in range(row + 1):
            if col == 0:
                dp[row][col] = dp[row - 1][col] + traingle[row][col]
                dp_path[row][col] = dp_path[row - 1][col] + f'-->[{row}, {col}]'
            elif col == row:
                dp[row][col] = dp[row - 1][col - 1] + traingle[row][col]
                dp_path[row][col] = dp_path[row - 1][col - 1] + f'-->[{row}, {col}]'
            else:
                dp[row][col] = min(dp[row - 1][col], dp[row - 1][col - 1]) + traingle[row][col]
                dp_path[row][col] = (dp_path[row - 1][col] if dp[row - 1][col] < dp[row - 1][col - 1] else dp_path[row - 1][col - 1]) + f'-->[{row}, {col}]'
    min_dp = min(dp[n - 1])
    min_index = dp[n - 1].index(min_dp)
    min_path = dp_path[n - 1][min_index]
    return min_dp, min_path
infinite = 1000
tree = [
    [
        [5, 4, 6]
    ],
    [
        [6, 5],
        [6, infinite],
        [8, 7]
    ],
    [
        [9], [8]
    ],
    [
        [0]
    ]
    ]
num = ['S', 'A', 'B', 'C']
def path_minimum_total(tree, num) -> int:
    n = len(tree)
    dp = copy.deepcopy(tree)
    dp_path = copy.deepcopy(tree)
    dp[0][0] = 0
    dp_path[0][0] = ''
    for k in range(1, n):
        for ele_i in range(len(dp[k])):
            list_v = []
            for i in range(len(tree[k - 1])):
                list_v += [tree[k - 1][i][ele_i] + dp[k - 1][i]]
            dp[k][ele_i] = min(list_v)
            the_i = list_v.index(min(list_v))
            dp_path[k][ele_i] = ''.join(dp_path[k - 1][the_i]) + num[k - 1] + str(the_i + 1) + '-->'
    min_path = ''.join(dp_path[n - 1]) + num[-1]
    min_dp = min(dp[n - 1])
    return min_dp, min_path
print(path_minimum_total(tree, num))