回溯算法总结

leetcode算法题之回溯算法

回溯算法的定义

到达一个节点之后有一些选择，选择一个路径往下走，发现没有不能实现预期结果或者不是最优结果在退回至上一步，选择另外一条路径。（在枚举的过程寻找最优解）

1. 八皇后问题

题目描述

给定一个数值N，在N X N 的棋盘上然后满足八皇后的条件：任意两个皇后不在同一个行，不在同一个列，也不在任何一个对角线位置上。请你打印出N皇后的所有解法，其中用Q表示位置上是皇后，用“·”表示位置上没有放皇后。

解题思路
下面放出一张图，通过这张图片来说明白解题目的思路

看到上面这张图，必然离不开递归的思想在里面：从一个节点下到下面的一个子节点有N中选择，每个子节点处又要执行同样的操作。

所以回溯类问题解体的思路如下：

void Backtracking(函数参数表)
{
    if(终止条件)
    {
        存放结果
        return；
    }
    for(选择：本层集和中的元素也就是当前节点子节点数目)
    {
        处理操作
    }
    Backtrack(新的函数列表)；//递归思想
    回溯撤销处理结果
}

上面的描述是N皇后进行回溯的过程，主要是先初始化定义一个棋盘结果vector,这个容器可以用来存放N个字符串，每个字符串又有N个字符，而且初始化这个字符串容器的每个内容存放的字符为 ‘·’

1 2	//初始化目标棋盘 vector<string> chessboard(n,string(n,'.'));

总体的求解问题的思路大致如下：

首先定义目标返回数组 result，中间棋盘数组：chessboard，backtrack()函数声明，重点是内部中传递的参数。
按照回溯算法的核心思想backtrack函数（①判断结束条件②做选择并在选择内判断是否继续往下面一项进行，是否进行继续操作③更新选择与条件，继续backtrack④撤销结果）

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        result.clear();
        vector<string> chessboard(n, string(n, '.'));
        Backtrack(n, 0, chessboard,result);
        return result;

    }
private:
    //从第一行开始往后面去判断
    void Backtrack(int n,int row,vector<string> &chessboard,vector<vector<string>> &result)
    {
        //是否走到了最后一行了（0-n-1,但是最后一个row+1正好为n）,能成立说明前面都满足放皇后的条件
        if(row==n)
        {
            result.push_back(chessboard);
            return ;
        }
        //在第row行，对尝试在每一列放置皇后
        for(int col=0;col<n;col++)
        {
            //验证每一列放置后的合法性，如果合法，更新一下位置“Q”，就可以继续研究下一行下一行
            if(IsValid(row,col,chessboard,n))
            {
                chessboard[row][col]='Q';
                Backtrack(n,row+1,chessboard,result);//如果一直成功，就一直执行道最后，放在result中。
                
                //跳出来Backtack说明目前选择的那一列可以放弃了，换下一列研究，因此将原本的Q改回来。
                chessboard[row][col]='.';
            }
        }
    }
    bool IsValid(int row,int col,vector<string> &chessboard,int n)
    {
        //检查列
        for(int i=0;i<row;i++)
        {
            if(chessboard[i][col]=='Q') return false;
        }
        //检查行
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--)
        {
            if(chessboard[i][j]=='Q') return false;
        }
        //检查列
        for(int i=row-1,j=col+1;i>=0&&j>=0;i--,j++)
        {
            if(chessboard[i][j]=='Q') return false;
        }
        return true;
    }
};

2.计算各个位不同数字的个数

题目描述：给定一个非负整数n,然后给出从0<<=x<<=10^n中各个位数字都不相同的个数。
自我感觉：这道题目像是动态规划的问题：

当n=0时，答案就是1，当n>10时，没有必要进行研究，相当于研究到n=10即可

第n个的答案为第n-1个答案再加上那N位的答案