Dynamic programming is equivalent to recursion + some way to remember the results (as far as I undertand) The y combinator allows to "tie" a previously "untied" recursion, which itself allows to compositionally inject additional steps in the recursion. This allows to go from recursion to dynamic programming in a structured way. This exemple is a bit contrived, as there are no overlapping subproblems, which would be the case in more interesting problem (dtw etc..)
2 people like thisPosted: 4 years ago by Nicolas2