Dynamic programming is a method for solving a bigger problem by breaking it down into smaller subproblems, solving each of those subproblems only once and storing their solutions. Next time the same subproblem occurs, instead of recomputing its solution, we simply look up the previously stored solution, hence saving computation time at the expense of some amount storage space. Each of the subproblem's solution is indexed/hashed in some way, normally based on the value of its input parameters, so as to facilitate lookup. The technique of storing solutions to subproblems instead of recomputing them is called "memoization". It is an optimization technique.
Divide and Conquer works in these steps.
Divide: Divide the main problem into small subproblems.
Conquer: Solve those subproblems recursively.
Combine: Combine results of subproblems to compute result of main problem.
Dynamic Programming is similar to Divide and Conquer when it comes to dividing bigger problems into smaller subproblems. But here, each subproblem is solved only once. In Divide and Conquer, the subproblems are independent of each other while in case of Dynamic Programming, subproblems are not independent of each other. Solution of one subproblem may be required to solve another subproblem. That is why in Dynamic programming solutions to subproblems are remembered. We store the result of subproblems in a table so that we don't have to compute the result of a subproblem again and again.
Divide and Conquer example: Merge Sort
Dynamic Programming example: Tower of Hanoi, Nth Fibonacci number
function fib(n)
if n <= 1 return n
return fib(n − 1) + fib(n − 2)
No comments:
Post a Comment