这个问题业界有专门研究。使用DP可以做到O(1.73^n)，DP+剪枝可以做到O(1.33^n)，这是目前做好的结果。不过这里的DP使用的切割线滑动方法，过于复杂，面试时肯定搞不了。

至于面试，直接DFS，然后开个多线程就完事了。在我的7年前笔记本(i7-6700HQ)上跑了一个，N=25，没有多线程用40s，开了12个线程，用了10秒（之所以没有按比例下降，是因为每个配置的路径数不同，不均衡）。

实际上还可以做点优化，就是利用对称性，可以成倍的减少计算量。这个还要研究一下。

多线程很简单，以N=4为基础(题目中直接给出了，12个配置，写死即可)，开12个，然后加起来即可。
use 12 thread calc for size = 25
size=25, number=4017128206,Time= 10.2935

use single thread calc for size = 25
size=25, number=4017128206,Time= 41.4999

这个是多线程代码

#include <iostream>
#include <vector>
#include <chrono>
#include <stack>
#include <thread>
#include <unordered_map>
#include <string>
using namespace std;

class solution
{
public:
    solution(int n, int _cfgno = -1)
    {
        N = n;
        Total = 0;
        memset(visited, 0, sizeof(visited));
        if (_cfgno == -1)
        {
            visited[0][0] = true;
            visited[1][0] = true;
            start_x = 1;
            start_y = 0;
            start_depth = 1;
        }
        else
        {
            auto cfg = init_cfg[_cfgno];
            for (int i = 0; i < 5; i++)
            {
                visited[cfg[i][0]][cfg[i][1]] = true;
            }
            start_x = cfg[4][0];
            start_y = cfg[4][1];
            start_depth = 4;
        }
    }

    unsigned int calc()
    {
        dfs(start_x, start_y, start_depth);
        return Total;
    }

private:
    int N;
    unsigned int Total;
    int start_x, start_y, start_depth;
    bool visited[26][26];
    int dirs[4][2] = { {1, 0}, {-1,0}, {0,1}, {0,-1} };

    int init_cfg[12][5][2] = {
        {{0,0},{1,0},{1,1},{1,2},{1,3} }, //0
        {{0,0},{1,0},{1,1},{1,2},{0,2} }, //1
        {{0,0},{1,0},{1,1},{1,2},{2,2} }, //2
        {{0,0},{1,0},{1,1},{0,1},{0,2} }, //3
        {{0,0},{1,0},{1,1},{2,1},{2,2} }, //4
        {{0,0},{1,0},{1,1},{2,1},{2,0} }, //5
        {{0,0},{1,0},{1,1},{2,1},{3,1} }, //6
        {{0,0},{1,0},{2,0},{2,1},{2,2} }, //7
        {{0,0},{1,0},{2,0},{2,1},{1,1} }, //8
        {{0,0},{1,0},{2,0},{2,1},{3,1} }, //9
        {{0,0},{1,0},{2,0},{3,0},{3,1} }, //10
        {{0,0},{1,0},{2,0},{3,0},{4,0} }, //11
    };

    void dfs(int x, int y, int depth)
    {
        unsigned int total_walks = 0;
        int new_x, new_y;
        for (int dir = 0; dir < 4; dir++)
        {
            new_x = x + dirs[dir][0];
            new_y = y + dirs[dir][1];
            if (new_x >= 0 && new_x <= N && new_y >= 0 && new_y < N)
            {
                if (!visited[new_x][new_y])
                {
                    if (depth == N - 1)
                    {
                        Total ++;
                    }
                    else
                    {
                        visited[new_x][new_y] = true;
                        dfs(new_x, new_y, depth + 1);
                    }
                }
            }
        }
        
        visited[x][y] = false;
        
    }
};

unsigned sum_part[12];
void thread_calc(int n, int i)
{
    solution* sln = new solution(n, i);
    sum_part[i] = sln->calc();
}

unsigned calc_path_number(int n, bool use_multi_thread)
{
    if (n < 5 || !use_multi_thread)
    {
        solution* sln = new solution(n);
        return sln->calc();
    }

    memset(sum_part, 0, sizeof(sum_part));

    vector<thread> pool;
    for (int i = 0; i < 12; i++)
    {
        pool.push_back(thread(thread_calc, n, i));
    }

    for (auto& t : pool)
    {
        t.join();
    }

    unsigned int sum = 0;
    for (int i = 0; i < 12; i++)
    {
        sum += sum_part[i];
    }
    return sum;
}

int main()
{
    int n = 25;

    std::cout << "use 12 thread calc for size = " <<n << endl;
    auto ts = chrono::high_resolution_clock::now();
    auto sum = calc_path_number(n,true);
    auto td = chrono::high_resolution_clock::now();
    float tt = chrono::duration<float, std::milli>(td - ts).count() / 1000.;
    std::cout << "size=" << n << ", number=" << sum << ",Time= " << tt << endl<<endl;

    std::cout << "use single thread calc for size = " << n << endl;
    ts = chrono::high_resolution_clock::now();
    sum = calc_path_number(n, false);
    td = chrono::high_resolution_clock::now();
    tt = chrono::duration<float, std::milli>(td - ts).count() / 1000.;
    std::cout << "size=" << n << ", number=" << sum << ",Time= " << tt << endl;
}




【 在 stub 的大作中提到: 】
: dfs很简单, 但是有 1s限制, dfs会超时
--
FROM 140.206.195.*