Divide and conquer: find sub-solutions, then combine them, e.g. take the minimum or maximum of the sub-solutions as the solution to the original problem

//
//  main.cpp
//  Minimum distance to make two arrays identical
//
//  Created by moule on 2022/9/3.
//

#include <iostream>
#include <vector>
using namespace std;
int minimal_distance(vector<int>& num1, vector<int>& num2, int idx1, int idx2){

    if(idx1 == num1.size() && idx2 == num2.size()){
        return 0;
    }
    if(idx1==num1.size() && idx2 != num2.size()){
       // cout << idx2 << endl;
        int k = num2[idx2] + minimal_distance(num1, num2, idx1, idx2+1);
        return k;
    }
    if(idx2==num2.size() && idx1 != num1.size()){
       // cout << idx2 << endl;
        return num1[idx1] + minimal_distance(num1, num2, idx1+1, idx2);

    }
    // delete num1[idx1]

    int p1 = num1[idx1] + minimal_distance(num1, num2, idx1+1, idx2);
 //   cout << p1;
    // delete num2[idx2]
    int p2 = num2[idx2] + minimal_distance(num1, num2, idx1, idx2+1);
   // cout << p2;
//    // num1[idx1] - num2[idx2]
    int p3 = abs(num1[idx1]-num2[idx2]) + minimal_distance(num1, num2, idx1+1, idx2+1);


    return min((p1,p2),p3);
}
int main(int argc, const char * argv[]) {
    // insert code here...
    vector<int> num1 = {2,3};
    vector<int> num2 = {2,3,5};
    cout << minimal_distance(num1, num2, 0, 0) << endl;
    std::cout << "Hello, World!\n";
    return 0;
}

E.g. the Tower of Hanoi: its subproblems need no combining; all the sub-solutions together form the solution to the whole problem

The subproblems of the Tower of Hanoi are as follows:

- 1) Move N-1 disks to the auxiliary peg
- 2) Move the Nth disk to the target peg
- 3) Move the N-1 disks on the auxiliary peg to the target peg, using the currently free peg.

Subproblems for making two arrays identical

- 1) Delete the element at the current index of the first array
- 2) Delete the element at the current index of the second array
- 3) Remove the difference between the values at the corresponding indices of the two arrays
Combine: take the sub-solution with the lowest cost of the three