De la cost[i] la cost[i+1], denumind linia curenta cu dp[], tranzitiile se pot scrie asa:
- dp[j] += |j|: sunt |j| unitati de flux pe muchia i - i+1
- dp'[j] = min(dp[j], dp[j - 1]): trimite 1 unitate de flux de la i+1 la Destinatie
- dp'[j] = min{non-negative p}(dp[j - p] + p * lambda): cumpara p unitati
- dp'[j] = dp[j + input[i + 1]]: sunt input[i + 1] unitati de flux venind dinspre Sursa
Gasiti o metoda de a implementa aceste operatii in timp O(1) amortizat.
