Skip to main content
Practice

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.


Characteristics​

  • 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.


What is Divide and Conquer?​

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.


Characteristics​

  • 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.


Differences​

  • 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.

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.