Optimal Division

这道题乍看是一个类似CLRS中matrix-chain multiplication的问题，实际上仔细分析以后是一个数学问题。分三种情况

• 只有一个数X1

• 有两个数X1/X2

• 三个数的时候，可以知道X1/X2/X3/X..的时候，最理想的情况是X1做nominator，X2做denominator，x3...xk作乘数，这题一个重要假设是所有数字都是正整数。如果这道题放宽条件，数字可以有+有-甚至有小树，则要用搜索或者DP。

public class Solution {
    public String optimalDivision(int[] nums) {
        StringBuilder builder = new StringBuilder();
        builder.append(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            if (i == 1 && nums.length > 2) {
                builder.append("/(").append(nums[i]);
            } else {
                builder.append("/").append(nums[i]);
            }
        }

        return nums.length > 2 ? builder.append(")").toString() : builder.toString();
    }
}

Matrix Chain Multiplication (recursion and DP)