3 ms·
Can you give me a solution involving inverting the execution order? It's the first time I read about it.
by zuzuleinen 4y ago
Can you give me a solution involving inverting the execution order? It's the first time I read about it.
- puffoflogic 4y agoConsider the trace of a naive recursive Fibonacci function: fib(5), fib(4), fib(3), fib(2), fib(1), fib(0), fib(1), fib(2), fib(1), fib(0), .... A memoized solution would merely eliminate the duplicates, but a DP solution should instead have this trace: fib(0), fib(1), fib(2), fib(3), fib(4), fib(5). With the DP solution we know a priori which terms will be needed, so we visit them in an order so that every term needed any step is already computed.