这道题乍看是一个类似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();
}
}