[reader5000]

In "Algorithms" [Dasgupta, Papamdimitriou, Vazirani] they state that the memoization (e.g. querying a hash table) can have significant overhead leading to a large constant factor in the big O analysis. On the other hand, the bottom up approach using a table solves all the possible subproblems including ones that are not needed and ones that the recursive approach would avoid. So from a big O perspective the recursive top-down and the table bottom-up approaches are the same but there can be significant constant factor differences.

[UncleMeat]

Then mention this in the interview. I ask an algorithms question that would likely be hated on HN but when candidates tell me the practical difference (API cleanliness, maintainability, performance, extensibility) between approaches that ultimately don't impact asymptotic runtime I love it.

[baobabKoodaa]

This is true. However, both approaches are "dp" if we are talking about the equivalent solution implemented in these different ways.

[reader5000]

Yeah I thought the recursion+memo wasn't actually "dp" until I looked it up. Recursion without the memo is not DP however since you hit exp running time/memory and the whole point of DP is to avoid this.