12月 3 2015

tech

Arithmetic Puzzles

Arithmetic Puzzles：给定一个由字母组成的等式，其中每一个字母表示一个数字。不同字母表示的数字一定不同。问字母和数字之间是否存在一一对应关系，使得等式成立。若存在多种方案输出按字母顺序排列后字典序最小的解。

比如 SEND+MORE=MONEY 的一个解为 9567+1085=10652。

题目的完整描述如下，来自hihocoder：

描述
Arithmetic puzzle is a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters. The goal is to identify the value of each letter. – wikipedia

For example, SEND+MORE=MONEY is a famous one of such puzzles. The solution is 9567+1085=10652. Note that different letters should represent different digits and the leading digit of a multi-digit number shoud not be zero.

Given an arithmetic puzzle, please find the solution.

输入
The first line contains an integer T(1 <= T <= 10), the number of puzzles.

N lines follow. Each line contains a puzzle. A puzzle consists of only ‘+’, ‘=’ and capital letters. The length of each puzzle will not exceed 100.

输出
For each puzzle output one line. If there is no solution output “No Solution” without qoutes, otherwise output the first solution by alphabetical order.

样例输入
4
A+B+C=AB
A+B+C=A+B
IOOOOOOOOOOOOOOOOOOOOOOOOO=IOOOOOOOOOOOOOOOOOOOOOOOOO
C=A
样例输出
1+0+9=10
1+2+0=1+2
10000000000000000000000000=10000000000000000000000000
No Solution

解题思路

根据题意我们可以得到下面几个条件：

最多只会有10个数字，所以解的组合数不超过 10!=3,628,800
最多允许存在10个字母，否则一定是No Solution
当单词长度超过1时，其首字母肯定不为0

一个简单的解法

首先我们需要将所有字母都找出来，按照字典序排列。再从第一个字母开始按字典序枚举数字，当给每一个字母分配了数字之后，将其带入等式，检查是否相等。

枚举数字时需要注意有的字母不能等于0，这一步我们可以在预处理中完成，用数组notZero表示该字母是否不能为0。

那么可以写出伪代码：

dfs(letter):  // for every letter
    startNum = 0  // 从0开始枚举
    If (notZero[ letter ]) Then   // 不能为0，则从1开始
        startNum = 1
    End If
    For i = startNum ... 9
        If not useNum[i] Then     // 数字i未使用过
            useNum[i] = true
            val[ letter ] = i     // letter对应数字 i
            If letter is last letter Then   // 如果是最后一个letter
                If (check(val)) Then
                    Return True   // 得到一个解
                End If
            Else 
                If (dfs(next letter)) Then   // 枚举下一个letter
                    Return True
                End If
            End If
            // 重置i和letter的状态
            val[ letter ] = -1
            useNum[i] = false
        End If
    End For
    Return False

val表示每个字母对应的数字，初始化为-1
useNum表示已经使用了的数字，初始为为false
check(val)表示将现在的val带入原公式检查是否合法

由于等式长度最大为100，有可能出现两个长度为49的数字进行比较，显然无法正常的采用转化为整数再进行比较的方法。

对于这样的情况，我们有如下的解决方案：

首先将等式右边的单词全部移到左边，这样公式就变成了形如：

word1 + word2 + … + word4 - word5 - word6 - … - word8 = 0

举个例子：SEND+MORE-MONEY=0

将其写成笔算的形式

+  SEND
+  MORE
- MONEY
------------
            0

接下来我们从最低位开始，一位一位向高位进行计算。假设前一位的进位为w，则当前位的总和为当前位所有出现过的字母之和加上w。最低位时，因为肯定没有进位，所以w = 0。

每一位的和为：s = D + E - Y + w。

由于我们之前已经枚举出了所有字母表示的数字，因此我们可以直接得到这个和s。

由于我们要使得最后的结果为0，所以s的末尾一定需要为0。

因此判定合法的条件为s % 10 == 0。

若s满足末尾为0，则我们可以继续向高位计算，新的进位为w = s / 10。

当计算到最高位时，不能产生进位，还需要额外判断s = 0。

伪代码为：

check(val)
    w = 0
    For i = low order .. high order       // 从低位像高位计算
        s = sigma(digit at order i) + w   // val
        If (s % 10 != 0) Then
            Return False
        End If
        If (i == high order && s != 0) Then
            Return False
        End If
        w = s / 10   // 进位
    End For
    Return True

假设一共出现了m个字母，n种字母。则该算法枚举组合的时间复杂度为 O(10! / (10 - n)!) ~= O(10!)，检查是否合法的时间复杂度为 O(m)，总的时间复杂度为 O(10!*m)

对于给定的时间限制肯定是会TLE的，因此我们需要对其进行优化。

代码一

上述算法的代码如下：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <ctime>
using namespace std;

string str;
vector<int> val(128, -1);        // 每个字母对应的数字， 默认-1
vector<bool> useNum(10, false);    // 是否使用过该数字
vector<bool> notZero(128, false);  // 是否可以为0，不能：true， 能：false
struct Word
{
    string num;
    int sign;   // 1:+, -1:-
}; 
vector<Word> words;
vector<char> letters;

// initialize variables
void init()
{
    words.clear();
    letters.clear();
    val.assign(128, -1);
    notZero.assign(128, false);
    useNum.assign(10, false);

    bool haveLetter[128] = {false};
    int flag = 1;   //+
    int sign = 1;
    int pre = 0, i = 0, n = str.size();
    for(; i < n; i++) 
    {
        char c = str[i];
        if(c == '+' || c == '-' || c == '=' ) 
        {
            words.push_back({str.substr(pre, i - pre), sign});
            if(c == '-')
                sign = -flag;
            else if(c == '=')
            {
                flag = -flag;
                sign = flag;
            }   
            if(i - pre > 1) 
                notZero[str[pre]] = true;
            pre = i + 1;
        }
        else
            haveLetter[c] = true;
    }
    words.push_back({str.substr(pre, n - pre), sign});
    for(int i = 0; i < words.size(); i++)
        reverse(words[i].num.begin(), words[i].num.end());
    if(n - pre > 1)
        notZero[str[pre]] = true;
    for(int c = 0; c < 128; c++)
        if(haveLetter[c])
            letters.push_back(c);
}

// check the value
bool checkVal()
{
    int w = 0, s = w;
    bool endFalg = false;
    int id = 0;
    while(!endFalg)
    {
        endFalg = true;
        s = w;
        for(auto word : words)
        {
            if( id < word.num.size() )
            {
                s += val[word.num[id]] * word.sign;
                endFalg = false;
            }
        }
        if(s % 10 != 0)
            return false;
        w = s / 10;
        id++;
    }
    return s == 0;
}

// display the result
void disp()
{
    for(auto c : str)
    {
        if( c != '+' && c != '-' && c != '=' )
            cout << val[c];
        else
            cout << c;
    }
    cout << endl;
}

// depth first search
bool dfs(int idx)
{
    char letter = letters[idx];
    int startNum = 0;
    if(notZero[letter])
        startNum = 1;
    for(int i = startNum; i <= 9; i++)
    {
        if( !useNum[i] )
        {
            useNum[i] = true;
            val[letter] = i;
            if(idx == letters.size() - 1)
            {
                if(checkVal())
                {
                    return true;
                }   
            }
            else
            {
                if(dfs(idx + 1))
                    return true;
            }
            useNum[i] = false;
            val[letter] = -1;
        }
    }
    return false;
}

int main()
{
    while(cin >> str)
    {
        clock_t t = clock();
        init();

        if( !dfs(0) )
            cout << "no solution\n";
        else
            disp();
        t = clock() - t;
        cout << "Elapse " << t  << " ms" << endl;
    }
    return 0;
}

对SEND+MORE=MONEY的运行时间为 780 ms。

优化一

在上面的算法中，我们是按照字母顺序以及字典序开始搜索。总是在枚举完全部的字母后，才进行匹配。然而实际上我们会遇到这样的情况：

比如DCBA+DCCA-DDDA=0，当我们枚举出A的值时，已经可以判定等式最后一位是否能够满足要求。但是在上面的算法中，我们并没有这么做，而是一直在枚举后面的字母。

因此我们提出一个改进的方法，我们按照从低位到高位的过程中，字母出现的顺序去枚举。这样做有一个好处和一个坏处：

好处是，能够在最短时间内检查出是否合法，而不需要去对整个等式进行检查。

坏处是，必须要枚举出所有可能的组合情况，并从中选取字典序最小的情况。

但实际上，由于该方法剪枝的强度比较大，所以对于大多数情况都能够很好的解决。除了一种特殊的情况，这个我们会在优化二中讲到。

该算法的实现要点：

根据笔算公式

 + SEND
+ MORE
-MONEY

从右到左，从上到下，同时计算w和s的值。设最大的位数为m位，一共有n个单词。我们用(i,j)来表示当前枚举到了右起第i位，上起第j个字母。比如在上面例子中(1,1)就是右上角的D，(2,3)就是MONEY中的E。

当枚举到的字母(i,j)尚未赋值时，枚举它可能出现的值；否则直接使用已经枚举的值。
当j = n + 1 时，表示该位所有的字母都已经枚举完毕，此时计算 w 和 s 并根据结果，决定是否递归计算(i+1,1)。
当i = m + 1时，表示所有位置都已经枚举完毕，此时根据进位的w是否等于0，来判定当前解是否合法。

伪代码实现为：

dfs(i, j, s):
    If (i == m + 1) Then    // 所有位置都枚举完
        If (s == 0) Then
            UpdateAns()
        End If
        Return 
    End If
    If (j == n + 1) Then    // 该位所有字母都已经枚举完
        If (s % 10 == 0) Then
            dfs(i + 1, 1, s / 10) // 直接将w加入s
        Else
            Return 
        End If
    End If
    letter = getLetter(i, j)   // 获得（i,j）处的字母
    If (val[ letter ] != -1) Then    // 该字母尚已赋值
        dfs(i, j + 1, s + val[ letter ] * op[j])
    Else
        startNum = 0
        If (notZero[ letter ]) Then 
            startNum = 1
        End If
        For i = startNum .. 9
            If not useNum[i] Then
                useNum[i] = true
                val[ letter ] = i
                dfs(i, j + 1, s + val[ letter ] * op[j])
                val[ letter ] = -1
                useNum[i] = false
            End If
        End If
    End If

优化一代码如下：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <ctime>
using namespace std;

class ArithmeticPuzzles
{
public:
    ArithmeticPuzzles(const string s);
    ~ArithmeticPuzzles(){};

    void init();                      // 对变量进行初始化
    void dfs(int i, int j, int s);    // 深度搜索
    void disp();                      // 显示结果
    char getLetter(int i, int j);     // 获得(i,j)处的字母
    void UpdateAns();                 // 更新结果/答案

private:
    string equation;
    std::vector<int> value;       // 每个字母对应的数字， 默认-1
    std::vector<bool> useNum;     // 是否使用过该数字
    std::vector<bool> notZero;    // 是否可以为0，不能：true， 能：false
    std::vector<string> nums;     // 以运算符分开的数字
    std::vector<int> operators;   // 运算符，与nums对应
    std::vector<char> letters;    // 出现的字母
    std::vector<int> result;      // 结果：保存字母对应的数字
    int n;              // 单词数量  
    int maxLength;      // 单词最大长度
    bool hasAnswer;     // 是否有解
};

ArithmeticPuzzles::ArithmeticPuzzles(string str) : equation(str)
{
    value.resize(128, -1);
    result.resize(128, -1);
    useNum.resize(10, false);
    notZero.resize(128, false);
    nums.clear();
    operators.clear();
    n = 0;
    maxLength = 0;
    hasAnswer = false;
}

void ArithmeticPuzzles::init()
{
    bool haveLetter[128] = {false};
    int flag = 1;   //+
    int sign = 1;
    int pre = 0, i = 0, len = equation.size();
    for(; i < len; i++) 
    {
        char c = equation[i];
        if(c == '+' || c == '-' || c == '=' ) 
        {
            nums.push_back(equation.substr(pre, i - pre));
            operators.push_back(sign);
            maxLength = max(i-pre, maxLength);
            if(c == '-')
                sign = -flag;
            else if(c == '=')
            {
                flag = -flag;
                sign = flag;
            }   
            if(i - pre > 1) 
                notZero[equation[pre]] = true;
            pre = i + 1;
        }
        else
            haveLetter[c] = true;
    }
    nums.push_back(equation.substr(pre, len - pre));
    operators.push_back(sign);
    if(len - pre > 1)
        notZero[equation[pre]] = true;
    maxLength = max(len-pre, maxLength);
    n = nums.size();
    // 单词翻转
    for(int i = 0; i < n; i++)
        reverse(nums[i].begin(), nums[i].end());

    for(int c = 0; c < 128; c++)
        if(haveLetter[c])
            letters.push_back(c);
};


void ArithmeticPuzzles::disp()
{
    if( !hasAnswer )
        cout << "no solution\n";
    else
    {
        for(auto c : equation)
        {
            if( c != '+' && c != '-' && c != '=' )
                cout << result[c];
            else
                cout << c;
        }
        cout << endl;
    }
}

char ArithmeticPuzzles::getLetter(int i, int j)
{
    if(j > nums.size()-1 || i > nums[j].size()-1)
        return -1;
    return nums[j][i];
}

void ArithmeticPuzzles::UpdateAns()
{
    if(!hasAnswer)
    {
        result = value;
        hasAnswer = true;
        return;
    }
    for(char letter : letters)  // 按字典序
    {
        if(value[letter] < result[letter])
        {
            result = value;
            return;
        }
        else if(value[letter] > result[letter])
            break;
        else
            continue;
    }
}

void ArithmeticPuzzles::dfs(int i, int j, int s)
{
    if(i == maxLength)
    {
        if(s == 0)
        {
            UpdateAns();
        }
        return;
    }
    if(j == n)
    {
        if(s % 10 == 0)
        {
            dfs(i+1, 0, s/10);
        }
        return;
    }
    char letter = getLetter(i, j);
    if(letter == -1)    // 不存在
    {
        dfs(i, j+1, s);
        return;
    }   
    if(value[letter] != -1)
        dfs(i, j+1, s + value[letter]*operators[j]);
    else
    {
        int startNum = 0;
        if(notZero[letter])
            startNum = 1;
        for(int k = startNum; k <= 9; k++)
        {
            if( !useNum[k] )
            {
                useNum[k] = true;
                value[letter] = k;
                dfs(i, j+1, s + k*operators[j]);
                useNum[k] = false;
                value[letter] = -1;
            }
        }
    }
    return;
}

int main()
{
    string str;
    while(cin >> str)
    {
        clock_t t = clock();

        ArithmeticPuzzles arith(str);
        arith.init();
        arith.dfs(0, 0, 0);
        arith.disp();

        t = clock() - t;
        cout << "Elapse " << t  << " ms" << endl;
    }
    return 0;
}

对SEND+MORE=MONEY的运行时间为 2 ms。

优化二

上面优化搜索顺序之后的代码，比起第一种方法已经有了很大的改善，但是仍然有一种情况没有办法做到。当碰到下面这种形式时，就会超时：

A+B+C+D+E+F+G+HJJJJJJJJJJJJJJ=A+B+C+D+E+F+G+IJJJJJJJJJJJJJJ

对以上问题，前面两种方法的运行时间如下：

第一种方法：85239ms
优化一：12009ms

超时的原因是因为其中8个字母都在最低位出现了，所以全部进行了枚举。并且只有当计算到最高位时才能确定这两个数是否相等。
对于这种数据，我们仔细观察会发现其中ABCDEFGJ的值实际上无论等于多少都可以，需要注意的只有H和I的值。

举一个简单的例子：A+B+C=AB

由于等式左右两边都有在个位的B，所以B的取值并不会对计算个位的s产生影响。对于这样的字母我们称之为无用的字母。

对于上面那个会超时的例子，我们可以发现，除了H和I以外全部都是无用的字母。枚举他们的值完全是没有必要的，我们只在一个字母出现，并且有用时才去枚举它的值。

因此我们先做一次预处理，将所有无用的字母都标记出，在枚举时直接跳过。无用字母由每一列上的元素决定，比如 AAC+B=AB 在个位上B为无用字母，在十位上A为无用字母，在百位上没有无用字母。

当然这样做还有一个问题：某一种字母每一次出现都是无用的字母，那么当我们找到合法答案时，该字母并没有赋值。

此时我们将剩余的数字按照最小序依次赋值给它们即可。

因此原伪代码改为：

dfs(i, j, s):
    If (i == m + 1) Then
        If (s == 0) Then
            fillAns()   // 赋值剩余的数字
            UpdateAns()
        End If
        Return 
    End If
    If (j == n + 1) Then
        If (s % 10 == 0) Then
            dfs(i + 1, 1, s / 10) // 直接将w加入s
        End If
         Return 
    End If
    letter = getLetter(i, j) // 若该字母为无用的字母，则返回-1
    If (letter == -1) Then  // 处理无用的字母
        dfs(i, j + 1, s)
        Return ;
    End
    If (val[ letter ] != -1) Then
        dfs(i, j + 1, s + val[ letter ] * op[j])
    Else
        startNum = 0
        If (notZero[ letter ]) Then 
            startNum = 1
        End If
        For i = startNum .. 9
            If not useNum[i] Then
                useNum[i] = true
                val[ letter ] = i
                dfs(i, j + 1, s + val[ letter ] * op[j])
                val[ letter ] = -1
                useNum[i] = false
            End If
        End If
    End If

加上第二种优化之后，就解决特殊情况，也就能够顺利地通过所有的测试点了。

优化二的代码如下：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <ctime>
#include <map>
using namespace std;

class ArithmeticPuzzles
{
public:
    ArithmeticPuzzles(const string s);
    ~ArithmeticPuzzles(){};

    void init();                      // 对变量进行初始化
    void dfs(int i, int j, int s);    // 深度搜索
    void disp();                      // 显示结果
    char getLetter(int i, int j);     // 获得(i,j)处的字母
    void UpdateAns();                 // 更新结果/答案
    void fillAns();

public:
    std::vector<char> letters;    // 出现的字母
private:
    string equation;
    std::vector<int> value;       // 每个字母对应的数字， 默认-1
    std::vector<bool> useNum;     // 是否使用过该数字
    std::vector<bool> notZero;    // 是否可以为0，不能：true， 能：false
    std::vector<string> nums;     // 以运算符分开的数字
    std::vector<int> operators;   // 运算符，与nums对应
    std::vector<int> result;      // 结果：保存字母对应的数字
    vector<vector<char>> useLess; // 存储每一列上的无用字符
    int n;              // 单词数量  
    int maxLength;      // 单词最大长度
    bool hasAnswer;     // 是否有解
};

ArithmeticPuzzles::ArithmeticPuzzles(string str) : equation(str)
{
    value.resize(128, -1);
    result.resize(128, -1);
    useNum.resize(10, false);
    notZero.resize(128, false);
    nums.clear();
    operators.clear();
    n = 0;
    maxLength = 0;
    hasAnswer = false;
}

void ArithmeticPuzzles::init()
{
    bool haveLetter[128] = {false};
    // flag,sign用来确定单词的运算符
    int flag = 1;   
    int sign = 1;
    int pre = 0, i = 0, len = equation.size();
    for(; i < len; i++) 
    {
        char c = equation[i];
        if(c == '+' || c == '-' || c == '=' ) 
        {
            nums.push_back(equation.substr(pre, i - pre));
            operators.push_back(sign);
            maxLength = max(i-pre, maxLength);
            if(c == '-')
                sign = -flag;
            else if(c == '=')
            {
                flag = -flag;
                sign = flag;
            }   
            if(i - pre > 1) 
                notZero[equation[pre]] = true;
            pre = i + 1;
        }
        else
            haveLetter[c] = true;
    }
    nums.push_back(equation.substr(pre, len - pre));
    operators.push_back(sign);
    if(len - pre > 1)
        notZero[equation[pre]] = true;
    maxLength = max(len-pre, maxLength);
    n = nums.size();
    // 单词翻转
    for(auto & num : nums)
        reverse(num.begin(), num.end());
    // 按字典序排列的字母
    for(int c = 0; c < 128; c++)
        if(haveLetter[c])
            letters.push_back(c);

    // 寻找每一列上的无用字母
    for(int i = 0; i < maxLength; i++)
    {
        map<char,int> opCount;  // 该字母的运算符出现的次数，'+'记为1，'-'记为-1.
        for(int j = 0; j < n; j++)
        {
            if(i > nums[j].size()-1)
                continue;
            opCount[nums[j][i]] += operators[j];
        }
        vector<char> useLessCol;
        for(map<char,int>::iterator it = opCount.begin(); it != opCount.end(); it++)
        {
            if(it->second == 0)    // '+' 与 '-'次数相同
                useLessCol.push_back(it->first);
        }
        useLess.push_back(useLessCol);
    }
};


void ArithmeticPuzzles::disp()
{
    if( !hasAnswer )
        cout << "No Solution\n";
    else
    {
        for(auto c : equation)
        {
            if( c != '+' && c != '-' && c != '=' )
                cout << result[c];
            else
                cout << c;
        }
        cout << endl;
    }
}

char ArithmeticPuzzles::getLetter(int i, int j)
{
    // 判断是否存在
    if(j > nums.size()-1 || i > nums[j].size()-1)
        return -1;
    // 判断该字母是否为无用字母
    for(auto c : useLess[i])
        if(c == nums[j][i])
            return -1;
    // 否则
    return nums[j][i];
}

void ArithmeticPuzzles::fillAns()
{
    for(auto letter: letters)
        if(value[letter] == -1)   // 无用字母
        {
            int startNum = notZero[letter] ? 1 : 0;
            for(int i = startNum; i <= 9; i++)
                if(!useNum[i])
                {
                    value[letter] = i;
                    useNum[i] = true;
                    break;
                }
        }
}

void ArithmeticPuzzles::UpdateAns()
{
    if(!hasAnswer)
    {
        result = value;
        hasAnswer = true;
        return;
    }
    for(char letter : letters)  // 按字典序比较
    {
        if(value[letter] < result[letter])
        {
            result = value;
            return;
        }
        else if(value[letter] > result[letter])
            break;
        else
            continue;
    }
}

void ArithmeticPuzzles::dfs(int i, int j, int s)
{
    if(i == maxLength)  // 最后一位
    {
        if(s == 0)
        {
            fillAns();
            UpdateAns();
        }
        return;
    }
    if(j == n)      // 每一位上的最后一个数
    {
        if(s % 10 == 0)
        {
            dfs(i+1, 0, s/10);   // 进入下一位,s/10表示进位
        }
        return;
    }
    char letter = getLetter(i, j);
    if(letter == -1)    // 无用的字母或不存在
    {
        dfs(i, j+1, s);
        return;
    }   
    if(value[letter] != -1)   // 该字母已赋值
        dfs(i, j+1, s + value[letter]*operators[j]);
    else
    {
        // 该字母未赋值，则枚举
        int startNum = notZero[letter] ? 1 : 0;
        for(int k = startNum; k <= 9; k++)
        {
            if( !useNum[k] )
            {
                useNum[k] = true;
                value[letter] = k;
                dfs(i, j+1, s + value[letter]*operators[j]);
                useNum[k] = false;
                value[letter] = -1;
            }
        }
    }
    return;
}

int main()
{
    int T;
    cin >>T;
    string str;
    while(T--)
    {
        cin >> str;
        ArithmeticPuzzles arith(str);
        arith.init();
        if(arith.letters.size() > 10)
        {
            cout << "No Solution\n";
            return 0;
        }
        arith.dfs(0, 0, 0);
        arith.disp();
    }
    return 0;
}

对SEND+MORE=MONEY的运行时间为 3 ms, 因为该表达式中没有出现无用字母，但对A+B+C+D+E+F+G+HJJJJJJJJJJJJJJ=A+B+C+D+E+F+G+IJJJJJJJJJJJJJJ的运行时间不到1ms，可以看出优化二对无用字母比较多的表达式处理很快。

题目总结

其实说了这么多，就两种思路解决本题。

思路一：按字典序给每一个字母赋值，然后带入表达式，如果正确，则结束运行，如果错误则进入下一个字典序。

思路二：先求解能满足表达式的结果，在结果中寻找字典序最小的一个并返回。

虽然只是在处理的顺序上不同了，但运行时间却很不同，第二种方法先求解满足表达式的结果，可以得到很大程度的剪枝，因为满足表达式的组合并不多，就算没有满足表达式的组合也能很快找到。然而，如果先遍历所有的字母组合，由于组合数太多，有10!个，最大的时间复杂度是O(10!)，是程序处理速度慢的主要原因。

本题是一道非常综合的题目，需要正确实现字符串处理、高精度加减法、深度优先搜索和一些剪枝优化，有不小的难度。

AllenYick's blog record the time | enjoy the life

解题思路

一个简单的解法

代码一

优化一

优化二

题目总结