reyg

Hm, here is an example:

// 1. Explore the possibility of a recurrence relation. If the problem can be solved as a function of sub problems, then candidate techniques are DP, backtracking, greedy, and divide/conquer

// 1a. Explore DP. If it’s DP, then optimal solutions of its subproblems are all that’s necessary. Confirm that subproblems are repeated so that I can reason for memoization and later leave room for a bottom up implementation.

// 1b. Explore backtracking. If it’s a backtracking problem, then I should be able to test for the viability of a partial solution quickly.

...and so on

A systematic approach like this or others (Gayle Laakmann Macdowell’s BUD) seem to reduce the risk of underperforming, but I haven’t had success with it. Instead, problem identification has been most helpful to me.

The approaches for solving Dynamic Programming problems are different than those that require a fundamental data structure (like a heap). Recognizing the heart of the problem is harder, probably what the interviewer is really testing for, and in my opinion differentiates oneself better than following a step by step guide.