But dp is a form of caching, no? It sacrifices space by caching intermediate results to compute successive results. The only reason it is called dp is because the "inventor" (Iirc Bell) needed a cool name.
DP is not a form of caching. DP is a way of breaking down a problem into subproblems. Caching (memoization) is one way to use this subproblem structure to reduce the amount of computation that ends up being performed in the end.
DP is a resolution technique that uses progressive (i.e. "dynamic") memoization (i.e. "programming" as in "tabulation", or resulting data stored in and retrieved from a table) as a way to curtail the cost of overlapping (i.e. intermediary and repetitive) subproblems. Memoization is a form of deterministic caching.
No, memoization is not caching. That’s a reductive understanding that causes no end of trouble.
Caching is global shared state. It brings nearly every problem that global shared state brings with it. If you conflate the two you miss all of the advantages of DP and “just use caches”.
Memoization in the scope of DP (some languages misuse the word in their APIs) is acknowledging that a problem is self recursive and eliminating the duplicate work by either inverting the problem or storing previously calculated values. These are usually call graph scoped. Nobody else sees the value. For instance in the case of solving Fibonacci with iteration, you need only remember the previous two values, which you store in registers. There is no table. There is no O(n) storage space.
Again, tabulation is when the contrast becomes stark. You’re creating an array where the relationship between the values contains information that makes the calculations cheap.
I don’t know what rock you’re living under but Redis is absolutely GSS, and any lookup table accessible between different tasks is shared state. In a language with threads anything the entire app can see is considered global shared state.
I think you misunderstand. DP is not equal to "caching", but in the set of all things that are "caching" DP is contained. I cannot think of any DP algorithm that does not explicitly or implicitly use a memory cache. Can you? Even in the case of DP Fibonacci the two registers of previous values constitute a cache.
