3 ms·
Step 1. ur problem graph better be a dag Step 2. ur sub problems better overlap Step 3. time to table dat dag Step 4. solve ur problems and build ur table gr
by kizer 8y ago
Step 1. ur problem graph better be a dag
Step 2. ur sub problems better overlap
Step 3. time to table dat dag
Step 4. solve ur problems and build ur table graph the way a dag would : to-po-lo-gi-cal-ly
- sumitgt 8y agoNice way to put it!
- akhilcacharya 8y agoI 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.
- myWindoonn 8y ago(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.