1. Divide and conquer

Divide and conquer is divide and conquer, that is, divide a problem into many sub-problems, and these problems and the original problem similar structure, and then solve the sub-problems recursively, finally merge the results of the sub-problems, get the results of the original problem.

There are three steps to divide and conquer:

Decomposition: The decomposition of a problem into subproblems similar in structure to the original problem

Solution: recursively solve each subproblem, when the subproblem is small enough, directly return the result (problem decomposition to small enough, decomposition termination conditions)

Merge: Combine the results of sub-problems to obtain the results of the original problem

Divide-and-conquer is also a recursion, and I’ve written about recursion templates, and I’ve posted a divide-and-conquer template here.

So let’s do a problem, let’s get into the divide-and-conquer algorithm a little bit, and let’s apply the template.

Pow(x,n)

Let’s first analyze this problem in three steps of divide-and-conquer:

Factorization: The NTH power of x can be factorized into subproblems: x^n/2…

Solution: the problem has not decomposed to the minimum, recursion, when the problem decomposed to enough hours, such as n=0, the result is 1; When n=1, the result is x; When n is equal to negative 1, it’s 1/x.

Merge: Combine the resulting results

When n % 2 = = 0 x ^ n = (x ^ n / 2) * (x ^ n / 2) when the n % 2 = = 1, x ^ n = x * (x ^ n / 2) * (x ^ n / 2)Copy the code

Here’s the code:

public double myPow(double x, int n) {
    // If the result is small enough, return the result directly
    if (n == 0) { return 1; }
    if (n == 1) { return x; }
    if (n == -1) { return 1 / x; }
    // Solve the subproblem recursively
    double half = myPow(x, n / 2);
    // call the module (considering that n may be negative)
    double rest = myPow(x, n % 2);
    // merge, return the result
    return rest * half * half;
}
Copy the code

This is the title of a typical divide-and-conquer algorithm, which decomposes the original problem, solves the subproblem (recursively, returning the result when the problem is small enough), and then merges the results of the subproblem.

2. Back

Backtracking utilizes the idea of trial and error, which attempts to solve a problem in steps. When a step calculation finds that the answer is wrong or invalid, it cancels the previous step, or even the previous steps, and then uses other step solutions to find the correct answer.

Eight queen

Let’s look at the classic eight Queens problem

Let’s talk about how to solve the problem, put this topic in this article, of course, is solved by recursive backtracking… Ok, next the hand tear eight empress ~

First of all, the title requires that each queen is not in the same line, in different rows, and not on the diagonal (in fact, the filtration condition given by the title). Different lines, in different rows, can be understood and solved easily. Let’s look at not on the diagonal (the diagonal line, the inverse diagonal line).

The sum of row and column indices is equal. (Image from LeetCode)

The diagonals have one feature: the difference between row and column subscripts is equal. (Image from LeetCode)

We need to enumerate the locations where the queen appears (can’t be attacked) and record the locations where the current queen position can be attacked.

A lot of analysis is written in the comments of the code, just look at the code

/** * N queen problem *@param n n
 * @return result
 */
public List<List<String>> solveNQueens(int n) {
    // Store the result set
    List<List<String>> solutions = new ArrayList<List<String>>();
    // Record the position of the queen
    int[] queens = new int[n];
    // Assign a default value
    Arrays.fill(queens, -1);
    // Record the queen's attack column
    Set<Integer> columns = new HashSet<Integer>();
    // Record the queen's attack and slash line
    Set<Integer> pie = new HashSet<Integer>();
    // Record the queen's attack slash
    Set<Integer> na = new HashSet<Integer>();
    // recursive call
    backtrack(solutions, queens, n, 0, columns, pie, na);
    // Return the result
    return solutions;
}

/** * a recursive function that enumerates the position of the queen *@paramSolutions result set *@paramQueens Columns (array records) that queens can place *@paramN n queens *@paramRow The current recursion is row 1 *@paramColumns Indicates the columns * that the queen can attack@paramPie has a queen that can attack the skew *@paramNa The slash that an existing queen can hit */
public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> pie, Set<Integer> na) {
    if (row == n) {
        // If the row is equal to n, the result set is exhausted
        List<String> board = generateBoard(queens, n);
        solutions.add(board);
    } else {
        // Iterate over all columns of the current row
        for (int i = 0; i < n; i++) {
            // The attacked column contains the first column, and the current column is skipped without further logic
            if (columns.contains(i)) {
                continue;
            }
            // The attacked slash line contains the current position and skips the current position
            if (pie.contains(row + i)) {
                continue;
            }
            // The hit slash contains the current position, skip the current position
            if (na.contains(row - i)) {
                continue;
            }
            // Record the current queen column
            queens[row] = i;
            // Records the columns hit by the current queen
            columns.add(i);
            // Record the current queen's attack on the skew line
            pie.add(row+i);
            // Record the current slash hit by the queen
            na.add(row-i);
            // call recursively, enumerating the queen position in the next row
            backtrack(solutions, queens, n, row + 1, columns, pie, na);
            /** * After the above recursion, the top down recursion is completed by enumerating all possible positions of one queen * and then cleaning up the previous data, enumerating all possible positions of the other queen */
            // Clear the columns stored by the queen
            queens[row] = -1;
            // Clear the queen attack column
            columns.remove(i);
            // Clean up the queen's attack and slash lines
            pie.remove(row+i);
            // Clear the queen's slashna.remove(row-i); }}}/ * * * *@paramQueens *@paramN N Queen *@returnPositions of all queens (with. And Q represent) */
public List<String> generateBoard(int[] queens, int n) {
    List<String> board = new ArrayList<String>();
    for (int i = 0; i < n; i++) {
        char[] row = new char[n];
        Arrays.fill(row, '. ');
        row[queens[i]] = 'Q';
        board.add(new String(row));
    }
    return board;
}
Copy the code

Did you fail after reading the code? The problem of eight Queens is mainly to illustrate the backtracking in recursion. When we enumerate a possibility and finally find that it is incorrect, we need to clean up the previous data, that is, cancel the operation of the previous step or even several steps. Get a sense of what it feels like to clean up data after a recursive function call (top-down) is complete.

conclusion

Divide and conquer: After a recursive call, to merge the results of the recursion.

Backtracking: After a recursive call, to cancel the previous step, many steps of the operation.

Divide-and-conquer and backtracking are both recursive in nature, and we need to analyze the specific problems, whether we need to decompose and combine the results, or constantly enumerate trial and error, and then backtrack.

Welcome to pay attention to the wechat public account “Mountain master”, the public account article first release, unlock more dry goods ~