Hacker Timesnew | past | comments | ask | show | jobs | submitlogin

I actually think overly focusing on the memoized recursion undermines the core conception of dynamic programming. Remember, as noted in the post, the term programming refers to a tabular method of planning, i.e. specifically, the bottom-up calculation to solve a problem. The emphasis here is on a predetermined order on how to tabulate the plan to get to the desired result which will be the solution to the broader problem.

The memoized recursive function is an implementation methodology on a digital computer that specifically side-steps the question of in which order one should do the tabulation. I would argue that recursive memoization is a possible solution technique to dynamic programming problems (defined as the universe of problems that admit a dynamic programming solution,) but strictly speaking, in and of itself, is not dynamic programming.



I'd actually go the other way round: figuring out a suitable recurrence relation is usually the first step in any dynamic programming solution. As a next step, sure, you can explicit construct a table to fill in, but that's not actually a requirement: dynamic programming also works when your parameters aren't things like numbers that you can easily use to enumerate rows in a table.

Memoisation is a more general tactic that hands more of the busy work over to the computer.




Consider applying for YC's Fall 2026 batch! Applications are open till July 27.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: