3 ms·
Actually the example given in the article cannot be further optimized, even when using dynamic programming. original: def cost(s): if s <= 1: retu
by crimsonalucard 8y ago
Actually the example given in the article cannot be further optimized, even when using dynamic programming.
original:
def cost(s):
if s <= 1:
return 0
if s % 2 == 0:
return 1 + cost(s // 2)
return min(1 + cost(s - 1), 5)
tabular:
def cost(s):
if s <= 1:
return 0
store = [None for _ in range(s+1)]
store[0] = 0
store[1] = 0
for i in range(2, s+1):
store[i] = 1 + store[i//2] if i%2 == 0 else min(1 + store[i-1], 5)
return store[-1]
Because of this step: store[i//2], the algorithm reaches back into the store dynamically meaning that there is no fixed amount of memory that the algorithm reaches back to retrieve old results. I cannot just save the old results in a fixed size list or fixed amount of variables. So this is the furthest you can go following the tabular path.