What is Dynamic Programming?

Dynamic Programming is an approach to solve complex problems by breaking them down into smaller sub-problems, storing the results of these sub-problems, and reusing them to enhance computational efficiency.

The process of storing the result of a sub-problem is called Memoization.

• Reusing Results: It stores the results of a problem once calculated and reuses them, preventing duplicate computations.

• Optimizing Sub-Problems: The optimal solution of a large problem is composed of the optimal solutions of its sub-problems.

Divide and Conquer is a strategy that solves a problem by dividing it into smaller sub-problems, solving each independently, and combining their solutions to solve the overall problem.

• Divide: Breaks the large problem into smaller ones.

• Conquer: Solves each small problem independently.

• Combine: Combines the solutions of the smaller problems to solve the overall problem.

• Redundancy of Problems: Dynamic Programming is efficient in solving overlapping sub-problems. In contrast, Divide and Conquer is more effective when sub-problems do not overlap.

• Memory Usage: Dynamic Programming uses additional memory to store computed results. However, Divide and Conquer generally doesn't require such storage.