Переменная не изменяется во время алгоритма рекурсивного возврата

Question

Я использую рекурсию и возврат для решения проблемы. Я обновляю переменную с именем minimum всякий раз, когда выполняется определенное условие. Однако, несмотря на то, что переменная minimum обновляется несколько раз при возврате функции, minimum по-прежнему имеет исходное значение.

Я не понимаю, почему, потому что я передаю ссылку на то же место в памяти и обновляю ее при попадании в базовый случай.

def minCost(self, costs: List[List[int]]) -> int:
        depth, cost, prev_index, minimum = 0, 0, None, 10000

        def min_cost_recur(depth, cost, prev_index, n, minimum, costs):
            if depth == n:
                minimum = min(minimum, cost)
                return

            original_prev_index = prev_index*1

            for i in range(0, 3):
                if not i == original_prev_index:
                    cost += costs[depth][i]
                    depth += 1
                    prev_index = i
                    min_cost_recur(depth, cost, prev_index, n, minimum, costs)
                    depth-=1
                    cost -= costs[depth][i]
                    prev_index = original_prev_index

        min_cost_recur(depth, cost, -1, len(costs), minimum, costs)

        return minimum

Answer 1

Вы должны вернуть новое значение minimum в вашей рекурсии, иначе оно никогда не обновится:

def minCost(self, costs: List[List[int]]) -> int:
        depth, cost, prev_index, minimum = 0, 0, None, 10000

        def min_cost_recur(depth, cost, prev_index, n, minimum, costs):
            if depth == n:
                minimum = min(minimum, cost)
                return minimum

            original_prev_index = prev_index*1

            for i in range(0, 3):
                if not i == original_prev_index:
                    cost += costs[depth][i]
                    depth += 1
                    prev_index = i
                    minimum = min(minimum, min_cost_recur(depth, cost, prev_index, n, minimum, costs))
                    depth-=1
                    cost -= costs[depth][i]
                    prev_index = original_prev_index
            return minimum
        minimum = min_cost_recur(depth, cost, -1, len(costs), minimum, costs)

        return minimum

Это происходит потому, что minimum передается не по ссылке, а по значению, так как это экземпляр неизменяемого типа. Когда вы изменяли его значение внутри рекурсии, он просто создавал локальное nmae для минимума, а не изменял переменную из родительской области.