zdps VS codility

I think their point is that naive caching attempts still result in duplicate work, and if you start by viewing the problem recursively then DP is a clever insight allowing you to avoid that duplicate work. You're right; it's not _just_ function calling overhead or anything minor; it often represents major Big-O improvements. I think that's in alignment with what they're saying.

I like your insight about Fibonacci needing less state than a naive DP would suggest. Diving into that a bit, DP implementations represent a DAG. More importantly, for all the problems that easily fit into DP that DAG has small numbers of "local" connections -- you can partition it into at least O(some_meaningful_dimension) many topologically sorted levels where each level only depends on a small, known, finite number of previous levels (often 1-2), not deeper DAG nodes. A clever choice of order of operations then looks for a min-cut on that graph, proceeding through those levels. Fib has at most O(n) levels and at least O(n) state for naive DP, so a clever implementation has O(n/n)=O(1) state. Edit distance has at most O(n) levels and at least O(n^2) state, so a clever implementation has O(n^2/n)=O(n) state. I did something similar for some DP probability calculation [0], and it reduces state from quadratic to linear.

Fibonacci is, slightly pedantically, one of the worst algorithms to analyze this way. Only the smallest inputs actually fit in machine integers, and the exponential increase in the size of any bigints involved really puts a damper on a naive Big-O analysis. Fib mod 2^64 (or some biggish prime) fits into the spirit of things better.

[0] https://github.com/hmusgrave/zdps

I remember learning about the knapsack problem and trying out recursive ways to solve it as well.

https://github.com/dsego/codility/blob/main/knapsack.js