Dynamic programming | dynamic | programming

Dynamic programming

Dynamic programming is like divide and conquer method in which problems are solved by combining the solution to sub problems. Divide and conquer algorithms divides the problems into sub problems and solves the sub problems recursively. These solved problems are then combined to solve original problem.
In dynamic programming sub problems are solved only one time. Sub solutions were saved in a table and this algorithm use these solutions to solve further problems.

Sub problems may have many solutions. Each solution has a value but we want to have a best solution of a problem.

•  The solution of a dynamic programming is quit complex.
•  The dynamic programming is used for complex problem.
•  The problems that satisfy the principle of optimality are suitable for dynamic programming solution.
•  Exponential time for a problem is unacceptable for large problems but it is useful for small problems.
• Time complexity of the dynamic programming is 0(N*k) where n is desire amount.