LeetCode刷题笔记(八): 分治

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

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

一、表达式问题

题目：为运算表达式设计优先级
给定一个只包含加、减和乘法的数学表达式，求通过加括号可以得到多少种不同的结果。

解答：

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> res;
        for (int i = 0; i < expression.length(); ++i) {
            if (expression[i] >= '0' && expression[i] <= '9')
                continue;
            vector<int> left = diffWaysToCompute(expression.substr(0, i));
            vector<int> right = diffWaysToCompute(expression.substr(i + 1));
            for (int l : left) {
                for (int r : right) {
                    int temp = 0;
                    switch (expression[i]) {
                    case '+':
                        temp = l + r;
                        break;
                    case '*':
                        temp = l * r;
                        break;
                    case '-':
                        temp = l - r;
                        break;
                    default:
                        break;
                    }
                    res.push_back(temp);
                }
            }
        }
        return res.empty() ? vector<int>{stoi(expression)} : res;
    }
};

提示：这里采用的是从上而下的分治，注意不是要每次都进行计算而是把left和right的结果先都存起来再进行计算。

二、练习

题目一：漂亮数组
如果长度为n的数组nums满足下述条件，则认为该数组是一个漂亮数组：

nums是由范围[1, n]的整数组成的一个排列。
对于每个0<=i<j<n，均不存在下标k(i<k<j)使得2*nums[k]==nums[i]+nums[j] 。
给你整数n，返回长度为n的任一漂亮数组。

解答：

class Solution {
public:
    vector<int> beautifulArray(int n) {
        if (n == 1) return {1};
        if (n == 2) return {1, 2};
        int mid = (n + 1) / 2;
        vector<int> left = beautifulArray(mid);
        vector<int> right = beautifulArray(n - mid);
        vector<int> res;
        for (int i = 0; i < mid; ++i)
            res.push_back(2 * left[i] - 1);
        for (int i = 0; i < n - mid; ++i)
            res.push_back(2 * right[i]);
        return res;
    }
};

解答二(动态规划)：

class Solution {
public:
    vector<int> beautifulArray(int n) {
        vector<vector<int>> dp(n + 1);
        dp[1] = {1};
        for (int i = 2; i <= n; ++i) {
            int mid = (i + 1) / 2;
            for (int j = 0; j < dp[mid].size(); ++j)
                dp[i].push_back(2 * dp[mid][j] - 1);
            for (int j = 0; j < dp[i - mid].size(); ++j)
                dp[i].push_back(2 * dp[i - mid][j]);
        }
        return dp[n];
    }
};

提示：动态规划还可以进行优化，这道题的关键是发现它的数学规律，f(n)=2*f(n/2)-1(奇数部分)，f(n)=f(n/2)*2(偶数部分)。

题目二：戳气球
戳破第i个气球，你可以获得nums[i-1]*nums[i]*nums[i+1]枚硬币。如果i-1或i+1超出了数组的边界，那么就当它是一个数字为1的气球。
求所能获得硬币的最大数量。

解答：

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        nums.push_back(1);
        nums.insert(nums.begin(), 1);
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = n - 3; i >= 0; --i) {
            for (int j = i + 2; j < n; ++j) {
                for (int k = i + 1; k < j; ++k) {
                    int sum = nums[i] * nums[k] * nums[j];
                    sum += (dp[i][k] + dp[k][j]);
                    dp[i][j] = max(dp[i][j], sum);
                }
            }
        }
        return dp[0][n - 1];
    }
};