Difference between Divide and Conquer, Decrease and Conquer and Dynamic Programming

Question

• What’s the difference between algorithm design techniques Divide and Conquer and Decrease and Conquer?
• To divide is recursive and the decrease nay?
• Some example for the decrease?
• And dynamic programming?

Answer 1

Hello! First it is important to note that all these techniques are based on induction.

Divide and conquer is an algorithmic design technique that consists of dividing the problem into smaller subproblems. These algorithms are divided into two phases: divisão and conquista. In the divisão, divide the problem in half (or in some fraction) and solve each subproblem. In the conquista, we combine the subproblems solutions to get the solution to the total problem. Examples of algorithms that use this technique are the MergeSort and the QuickSort.

Decrease and conquer is similar to divide and conquer, with the difference that in this technique the phase of decrease only lessens the problem by generating a minor subproblema (instead of dividing it into several subproblems). After solving the minor subproblema, the conquista is executed to use the subproblem solution to get the solution of the total problem. Examples of decrease and conquer sane Busca Binária (divide the vector in the middle and perform the search only on one side) and DFS. Algorithms of decrease and conquer may also be recursive, such as binary search.

Dynamic programming is a technique that uses memorization to solve subproblems. This technique makes sense when subproblems are repeated. An example of a problem that can be solved with dynamic programming is the fibonacci, for, fibonacci(N) = fibonacci(N-1) + fibonacci(N-2), fibonacci(N-1) = fibonacci(N-2) + fibonacci(N-3), and so on... Note that the subproblema fibonacci(N-2) is repeated. Dynamic programming consists of memorizing the sub-standard solutions so that they are not recalculated.
Another important thing is that dynamic programming can only be applied to problems with optimal substructure. Saying that a problem has optimal substructure means that an optimal solution to the larger problem contains the optimal solutions for the subproblems.

I’m leaving some references with more detailed explanations.

https://www.geeksforgeeks.org/decrease-and-conquer/
https://stackoverflow.com/questions/13538459/difference-between-divide-and-conquer-algo-and-dynamic-programming
https://en.wikipedia.org/wiki/Dynamic_programming

I hope I’ve helped.