给定一组正整数，相邻的整数之间将会进行浮点除法操作。例如， [2,3,4] -> 2 / 3 / 4 。

但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，才能得到最大的结果，并且返回相应的字符串格式的表达式。你的表达式不应该含有冗余的括号。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/optimal-division
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

递归

class Solution {

    private Info solve(int[] nums, int left, int right) {
        if (left == right) {
            return new Info(nums[left], String.valueOf(nums[left]), nums[right], String.valueOf(nums[right]));
        }
        if (left + 1 == right) {
            return new Info((double) nums[left] / nums[right], nums[left] + "/" + nums[right], (double) nums[left] / nums[right], nums[left] + "/" + nums[right]);
        }

        Info ans = new Info(Double.MAX_VALUE, null, Double.MIN_VALUE, null);

        for (int i = left; i < right; ++i) {
            Info info1 = solve(nums, left, i);
            Info info2 = solve(nums, i + 1, right);
            if (info1.minValue / info2.maxValue < ans.minValue) {
                ans.minValue = info1.minValue / info2.maxValue;
                ans.minOp = info1.minOp + "/" + (right - i == 1 ? info2.maxOp : ("(" + info2.maxOp + ")"));
            }

            if (info1.maxValue / info2.minValue > ans.maxValue) {
                ans.maxValue = info1.maxValue / info2.minValue;
                ans.maxOp = info1.maxOp + "/" + (right - i == 1 ? info2.minOp : ("(" + info2.minOp + ")"));
            }
        }
        return ans;
    }

    public String optimalDivision(int[] nums) {
        if (nums == null || nums.length == 0) {
            return "";
        }
        return solve(nums, 0, nums.length - 1).maxOp;
    }
}

class Info {
    double minValue;
    String minOp;
    double maxValue;
    String maxOp;

    public Info(double minValue, String minOp, double maxValue, String maxOp) {
        this.minValue = minValue;
        this.minOp = minOp;
        this.maxValue = maxValue;
        this.maxOp = maxOp;
    }
}

记忆化搜素

class Solution {

    private Info[][] dp;

    private Info solve(int[] nums, int left, int right) {
        if (dp[left][right] == null) {
            if (left == right) {
                dp[left][right] = new Info(nums[left], String.valueOf(nums[left]), nums[right], String.valueOf(nums[right]));
            } else if (left + 1 == right) {
                dp[left][right] = new Info((double) nums[left] / nums[right], nums[left] + "/" + nums[right], (double) nums[left] / nums[right], nums[left] + "/" + nums[right]);
            } else {
                Info ans = new Info(Double.MAX_VALUE, null, Double.MIN_VALUE, null);
                for (int i = left; i < right; ++i) {
                    Info info1 = solve(nums, left, i);
                    Info info2 = solve(nums, i + 1, right);
                    if (info1.minValue / info2.maxValue < ans.minValue) {
                        ans.minValue = info1.minValue / info2.maxValue;
                        ans.minOp = info1.minOp + "/" + (right - i == 1 ? info2.maxOp : ("(" + info2.maxOp + ")"));
                    }
                    if (info1.maxValue / info2.minValue > ans.maxValue) {
                        ans.maxValue = info1.maxValue / info2.minValue;
                        ans.maxOp = info1.maxOp + "/" + (right - i == 1 ? info2.minOp : ("(" + info2.minOp + ")"));
                    }
                }
                dp[left][right] = ans;
            }
        }
        return dp[left][right];
    }

    public String optimalDivision(int[] nums) {
        if (nums == null || nums.length == 0) {
            return "";
        }
        this.dp = new Info[nums.length][nums.length];
        return solve(nums, 0, nums.length - 1).maxOp;
    }
}

class Info {
    double minValue;
    String minOp;
    double maxValue;
    String maxOp;

    public Info(double minValue, String minOp, double maxValue, String maxOp) {
        this.minValue = minValue;
        this.minOp = minOp;
        this.maxValue = maxValue;
        this.maxOp = maxOp;
    }
}

动态规划

数学

class Solution {
    public String optimalDivision(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return String.valueOf(nums[0]);
        }
        if (n == 2) {
            return nums[0] + "/" + nums[1];
        }
        StringBuffer res = new StringBuffer();
        res.append(nums[0]).append("/(").append(nums[1]);
        for (int i = 2; i < n; i++) {
            res.append("/");
            res.append(nums[i]);
        }
        res.append(")");
        return res.toString();
    }
}