算法解释

顾名思义，分治问题由“分”（divide）和“治”（conquer）两部分组成，通过把原问题分为子问题，再将子问题进行处理合并，从而实现对原问题的求解。我们在排序章节展示的归并排序就是典型的分治问题，其中“分”即为把大数组平均分成两个小数组，通过递归实现，最终我们会得到多个长度为 1 的子数组;“治”即为把已经排好序的两个小数组合成为一个排好序的大数组，从长度为 1 的子数组开始，最终合成一个大数组。

另外，自上而下的分治可以和 memoization 结合，避免重复遍历相同的子问题。如果方便推导，也可以换用自下而上的动态规划方法求解。

表达式问题

为运算表达式设计优先级

给你一个由数字和运算符（只包含+，-，*）组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以按任意顺序返回答案。

生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104。

示例 1：

输入：expression = “2-1-1”
输出：[0,2]

示例 2：

输入：expression = “2*3-4*5”
输出：[-34,-14,-10,-10,10]
解释：
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

利用分治思想，我们可以把加括号转化为，对于每个运算符号，先执行处理两侧的数学表达式，再处理此运算符号。注意特殊情况，即字符串内无运算符号，只有数字。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> diffWaysToCompute(string input) {
    vector<int> ways;
    for (int i = 0; i < input.length(); i++) {
        char c = input[i];
        if (c == '+' || c == '-' || c == '*') {
            //分
            vector<int> left = diffWaysToCompute(input.substr(0, i));
            vector<int> right = diffWaysToCompute(input.substr(i + 1));
            //治
            for (const int & l: left) {
                for (const int & r: right) {
                    switch (c) {
                        case '+': ways.push_back(l + r); break;
                        case '-': ways.push_back(l - r); break;
                        case '*': ways.push_back(l * r); break;
                    }
                }
            }
        }
    }
    if (ways.empty()) 
        ways.push_back(stoi(input));	//stoi()函数将string类型转为int
    return ways;
}

我们发现，某些被 divide 的子字符串可能重复出现多次，因此我们可以用 memoization 来去重。或者与其我们从上到下用分治处理 + memoization，不如直接从下到上用动态规划处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
vector<int> diffWaysToCompute(string input) {
    vector<int> data;
    vector<char> ops;
    int num = 0;
    char op = ' ';
    // 将 input 划分成数据（data）和运算符（ops），后面加一个 "+" 方便处理
    istringstream ss(input + "+");
    while (ss >> num && ss >> op) {
        data.push_back(num);
        ops.push_back(op);
    }
    int n = data.size();
    // 三维 vector 数组
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>()));
    /*
    	dp[i][j] 是一个一维 vector 数组，里面存储着：从第 i+1 个数字到第 j+1 个数字组成的算式的所有可能的运算结果，
    	所以最后要输出的就是 dp[0][n-1]。
    */
    for (int i = 0; i < n; i++) {
        for (int j = i; j >= 0; j--) {
            // 如果 i == j，显然只有一种可能
            if (i == j)
                dp[j][i].push_back(data[i]);
            else {
                /* k 在 i 和 j 之间形成了一个 divide
                 举一个例子，有算式：1-2+3*4
                 当 i = 0, j = 3, k = 1 时，实际上就相当于计算这样一个算式的值：(1-2)+(3*4)，然后 push_back 到 dp[0][3] 里面
                 这样计数可以保证不重不漏
                */
                for (int k = j; k < i; k += 1) {
                    for (auto left : dp[j][k]) {
                        for (auto right : dp[k+1][i]) {
                            int val = 0;
                            switch (ops[k]) {
                                case '+': val = left + right; break;
                                case '-': val = left - right; break;
                                case '*': val = left * right; break;
                            }
                            dp[j][i].push_back(val);
                        }
                    }
                }
            }
        }
    }
    return dp[0][n-1];
}

练习

漂亮数组

对于某些固定的 N，如果数组 A 是整数 1, 2, …, N 组成的排列，使得：对于每个 i < j，都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。那么数组 A 是漂亮数组。

给定 N，返回任意漂亮数组 A（保证存在一个）。

示例 1：

输入：4
输出：[2,1,4,3]

示例 2：

输入：5
输出：[3,1,2,5,4]

观察表达式，发现左边恒为偶数，则要不满足，只需右边一奇一偶即可，所以可以把数组一分为二，奇数放左边，偶数放右边，现在只要左右两边分别是漂亮数组即可，则 1~N 的奇数或偶数分别可以双射到 1~(N+1)/2 和 1~N/2 的整数，容易证明，映射不影响漂亮数组的性质，所以问题被分解为两个更小规模的子问题，递归处理即可

代码

带 memoization 的分治法，自上而下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
map<int, vector<int>> memo;
vector<int> beautifulArray(int n) {
    if(memo.count(n))
        return memo[n];
    vector<int> res(n);
    if(n == 1)  
        res[0] = 1;
    else {
        int t = 0;
        for(int& x : beautifulArray((n + 1) / 2))
            res[t++] = 2 * x - 1;
        for(int& x : beautifulArray(n / 2))
            res[t++] = 2 * x;
    }
    memo[n] = res;
    return res;
}

当然可以动态规划，自下而上：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> beautifulArray(int n) {
    if (n == 1)
        return {1};
    vector<vector<int>> dp(n + 1, vector<int>());
    dp[1] = {1};
    dp[2] = {1, 2};
    for (int i = 3; i <= n; i++) {
        for (int j = 0; j < (i + 1) / 2; j++)
            dp[i].push_back(dp[(i+1)/2][j] * 2 - 1);
        for (int j = 0; j < i / 2; j++)
            dp[i].push_back(dp[i/2][j] * 2);
    }
    return dp[n];
}

戳气球

有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] nums[i] nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

示例 1：

输入：nums = [3,1,5,8]
输出：167

示例 2：

输入：nums = [1,5]
输出：10

为方便处理，把数组两端加上 nums[-1] 和 nums[n]，都等于 1，并保存在 rec 中，即 rec[i] = nums[i-1]，戳气球会导致原本不相邻的气球变成相邻的，所以我们反向考虑，添加气球，定义 solve(i, j) 表示在区间 (i, j) 内可获得的最大硬币数，则可以取一个中间的点 mid（这个mid必须放在最后戳破，因为只有这样可以消除两个子问题的相关性）分别求 solve(i, mid) 和 solve(mid, j)，然后相加即可，于是把原问题分解为了一个个子问题。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<vector<int>> dp; //记忆化
vector<int> rec; //记录气球值
int maxCoins(vector<int>& nums) {
    int n = nums.size();
    rec.push_back(1);
    for (int i = 0; i < n; i++)
        rec.push_back(nums[i]);
    rec.push_back(1);
    dp.resize(n + 2, vector<int>(n + 2, -1));
    return solve(0, n + 1); 
}
int solve(int l, int r) {
    if (l > r) 
        return 0; 
    if (dp[l][r] != -1) 
        return dp[l][r];
    for (int mid = l + 1; mid < r; mid++) {
        int sum = rec[mid] * rec[l] * rec[r];
        sum += solve(l, mid) + solve(mid, r);
        dp[l][r] = max(sum, dp[l][r]);
    }
    return dp[l][r];
}

当然可以使用自下而上的动态规划（dp[i][j] 表示 (i, j) 范围内最大硬币数）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxCoins(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> dp(n + 2, vector<int>(n + 2));
    vector<int> val(n + 2);
    val[0] = val[n + 1] = 1;
    for (int i = 1; i <= n; i++)
        val[i] = nums[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 2; j <= n + 1; j++) {
            for (int k = i + 1; k < j; k++) {
                int sum = val[i] * val[k] * val[j];
                sum += dp[i][k] + dp[k][j];
                dp[i][j] = max(dp[i][j], sum);
            }
        }
    }
    return dp[0][n+1];	
}