Hacker News Reader

I think the DAG approach is a good one, but the problem is its not great for being applied generally. For me, it's difficult to think of something like the "House Robber" problem as a DAG.

Can someone explain what DAG stands for? Thanks.

https://en.wikipedia.org/wiki/Directed_acyclic_graph

(Thanks)

(4) is what sets your approach apart from the OP. Solve the problem by searching through the graph, using standard graph search. The OP's "iterative" approaches are close, but they waste massive amounts of time by precomputing the entire table when they could search instead. Iteration with a stack is DFS; iteration with a FIFO queue is BFS; iteration with a priority queue is Dijkstra's if priorities are precise, or A* if priorities are admissible.

Nice way to put it!