Introduction to Computational Thinking: Problem Solving, Algorithms, Data Structures, and More

© The Author(s), under exclusive license to APress Media, LLC, part of Springer Nature 2021

T. MailundIntroduction to Computational Thinkinghttps://doi.org/10.1007/978-1-4842-7077-6_9

9. Divide and Conquer and Dynamic Programming

Thomas Mailund¹  

(1)

Aarhus N, Denmark

 

Divide and conquer is the algorithmic version of recursion. The term comes from the political doctrine divide et impera, but for algorithms, a more correct description would be divide and combine. The key idea is to

1. 1.

   Split a problem into subproblems of the same type.

    
2. 2.

   Recursively solve these problems.

    
3. 3.

   Combine the results of the recursive calls to a solution of the original problem.

    

Steps 1 and 3 can be trivial or complex, while step 2 is usually one or two recursive calls.

The binary ...