DP is a general technique for solving complex optimization problems that can be decomposed into overlapping subproblems. Like divide and conquer, we solve the problem by combining the solutions of multiple smaller problems but what makes DP different is that the subproblems may not be independent. A key to making DP efficient is reusing the results of intermediate computations. Problems which are natually solved using DP are a problem choice for hard interview questions.
The simplest DP probably is the solving Fibonacci number defined by Fn=Fn-1+Fn-2. If we don't store the Fn value, we need to compute Fn many times.
The key to solving any DP problem efficiently is finding the right way to break the problem into subproblems such that
--- the bigger problem can be solved relatively easily once solutions to all the subproblems are available, and
--- you need to sovle as few subproblems as possible
In some cases, this many require solving a slightly different optimization problem than the original problem.
No comments:
Post a Comment