Минимальный путь стоимость матрицы с помощью Python


Я читал эту статью о нахождении минимального по стоимости пути от (0,0) любой (m,n) точки в матрице. С помощью Python автор предлагает 2 решения в Python.

Первый решает ее с помощью обратной индукции метод с помощью рекурсии, в то время как второй использует вспомогательную таблицу (tc). Мне было интересно, если я мог бы решить это с помощью индукции и без необходимости дополнительной таблицы. Вот мое решение:

def test(target_matrix, cost, i, j, m, n):
    if (i == m and j == n):
        return cost
    if i+1 > m:
        cost += target_matrix[i][j+1] 
        return test(target_matrix, cost, i, j+1, m, n)
    if j+1 > n:
        cost += target_matrix[i+1][j] 
        return test(target_matrix, cost, i+1, j, m, n)
    if (i+1 <= m and j+1 <= n):
        ret_cost, i, j = min(target_matrix[i+1][j], target_matrix[i][j+1], target_matrix[i+1][j+1], i, j)
        cost +=ret_cost
        return test(target_matrix, cost, i, j, m, n)


def min(x, y, z, i, j):
    if (x < y):
        if (x < z):
            return x, i+1, j
        else:
            return z, i+1, j+1
    else:
        if (y < z):
            return y, i, j+1
        else:
            return z, i+1, j+1


if __name__ == '__main__':
    input = [
            [11,9, 3],
            [3, 1, 0],
            [1, 3, 2]
            ]
    res = test(input, input[0][0], 0, 0, 2, 2)
    print(res)

Каковы ваши комментарии по этому поводу? Как вы думаете, имеют свои недостатки по сравнению двух решений, предусмотренных в статье? Я особенно заинтересован в комментариях относительно временная и емкостная сложность алгоритма.



Комментарии