Задача: 465. Optimal Account Balancing
Сложность: medium

Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.
Верните минимальное количество транзакций, необходимых для урегулирования долгов.

Пример:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2

👨‍💻 Алгоритм:

1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека.

2⃣Собрать все ненулевые чистые балансы в массив balance_list.

3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]:
Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1.
Если cur = n, вернуть 0.
В противном случае установить cost на большое значение, например, inf.
Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0,
Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur].
Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1).
Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат).
Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации.
Вернуть cost, когда итерация завершена. Вернуть dfs(0).

😎 Решение:

class Solution {
    private $creditList;
    
    function minTransfers($transactions) {
        $creditMap = [];
        foreach ($transactions as $t) {
            if (!isset($creditMap[$t[0]])) $creditMap[$t[0]] = 0;
            if (!isset($creditMap[$t[1]])) $creditMap[$t[1]] = 0;
            $creditMap[$t[0]] += $t[2];
            $creditMap[$t[1]] -= $t[2];
        }
        
        $this->creditList = [];
        foreach ($creditMap as $amount) {
            if ($amount != 0) {
                $this->creditList[] = $amount;
            }
        }
        
        $n = count($this->creditList);
        return $this->dfs(0, $n);
    }
    
    private function dfs($cur, $n) {
        while ($cur < $n && $this->creditList[$cur] == 0) {
            $cur++;
        }
    
        if ($cur == $n) {
            return 0;
        }
        
        $cost = PHP_INT_MAX;
        for ($nxt = $cur + 1; $nxt < $n; $nxt++) {
            if ($this->creditList[$nxt] * $this->creditList[$cur] < 0) {
                $this->creditList[$nxt] += $this->creditList[$cur];
                $cost = min($cost, 1 + $this->dfs($cur + 1, $n));
                $this->creditList[$nxt] -= $this->creditList[$cur];
            }
        }
        
        return $cost;
    }
}

Ставь 👍 и забирай 📚 Базу знаний