3 ms·
Care to elaborate how do you go about problem identification?
by suyash 9y ago
Care to elaborate how do you go about problem identification?
- reyg 9y agoHm, 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
- abhirag 9y agoI think your example can be simplified :) Recursion + memoization provides most of the benefits of dynamic programming, including usually the same running time and well backtracking is recursion so the strategy can very well be -- Explore the possibility of a recurrence relation, if the possibility exists, try recursion :D
- thaumasiotes 9y agoSolve problems. Hopefully, after solving a problem several times, you'll be able to recognize it.