https://en.wikipedia.org/wiki/Longest_increasing_subsequence
https://en.wikipedia.org/wiki/Longest_common_subsequence_pro...
https://en.wikipedia.org/wiki/Dynamic_programming
Am I to understand that it is "just" recursion with caching?
I do recommend you to read this chapter:
https://people.eecs.berkeley.edu/~vazirani/algorithms/chap6....
After reading this chapter, you can try to understand why Dijkstra and Floyd-Warshall shortest path in graph algorithms work.
These classical and fundamental algorithms combine graph theory with dynamic programming.
Spotting where it can be successfully applied is the hard part.
Recursion not required, iterative DP solutions are things too.
Maybe you could explain better...?
[0] https://people.eecs.berkeley.edu/~vazirani/algorithms/chap6....
> Then why did recursion work so well with divide-and-conquer? The key point is that in divide-and-conquer, a problem is expressed in terms of subproblems that are substantially smaller, say half the size. For instance, mergesort sorts an array of size n by recursively sorting two subarrays of size n/2. Because of this sharp drop in problem size, the full recursion tree has only logarithmic depth and a polynomial number of nodes.
> In contrast, in a typical dynamic programming formulation, a problem is reduced to subproblems that are only slightly smaller—for instance, L(j) relies on L(j − 1).
I think I got it. The distinction isn't that clear cut anyway. For example, I could implement a mergesort with caching and say that I'm technically doing dynamic programming, even though the cache would get hit exactly zero times. It would sort of be "trivially" dynamic programming. On the other hand, the first time I calculated fibonacci numbers recursively, I've added a cache. This would be "memoization". Or in other words, wikipedia article is correct, but some problems don't benefit from the caching.
Thanks for the references.
"just caching" is also hard to apply to e.g. the tower of hanoi problem.