思路分治 记忆化对于表达式中的每一个运算符都可以把它作为最后一次运算将表达式分成左右两部分。分别递归求出左右两部分的所有可能结果再做笛卡尔积运算即可。例如 23-45以 - 为分割点· 左边 23 → [6]· 右边 45 → [20]· 组合 → [6-20] [-14]由于子表达式会被重复计算用 HashMap 做记忆化。解法一递归 记忆化推荐classSolution{publicListIntegerdiffWaysToCompute(Stringexpression){returndfs(expression,newHashMap());}privateListIntegerdfs(Stringexpr,MapString,ListIntegermemo){if(memo.containsKey(expr)){returnmemo.get(expr);}ListIntegerresnewArrayList();booleanisNumbertrue;for(inti0;iexpr.length();i){charcexpr.charAt(i);if(c||c-||c*){isNumberfalse;// 以当前运算符为最后一次运算分割成左右两部分ListIntegerleftdfs(expr.substring(0,i),memo);ListIntegerrightdfs(expr.substring(i1),memo);for(intl:left){for(intr:right){if(c)res.add(lr);elseif(c-)res.add(l-r);elseres.add(l*r);}}}}// 说明 expr 是一个纯数字if(isNumber){res.add(Integer.parseInt(expr));}memo.put(expr,res);returnres;}}复杂度这是 Catalan 数级别的问题第 n 个 Catalan 数约为 4^n / n^(3/2)即结果数量与时间复杂度同阶记忆化后主要成本在结果本身。解法二区间 DP自底向上先把表达式解析成数字数组和运算符数组然后按区间长度从小到大 DP。classSolution{publicListIntegerdiffWaysToCompute(Stringexpression){ListIntegernumsnewArrayList();ListCharacteropsnewArrayList();intcur0;for(inti0;iexpression.length();i){charcexpression.charAt(i);if(Character.isDigit(c)){curcur*10(c-0);}else{nums.add(cur);cur0;ops.add(c);}}nums.add(cur);intnnums.size();// dp[i][j] 表示 nums[i..j] 能形成的所有结果SuppressWarnings(unchecked)ListInteger[][]dpnewList[n][n];for(inti0;in;i){dp[i][i]newArrayList();dp[i][i].add(nums.get(i));}for(intlen2;lenn;len){for(inti0;ilen-1n;i){intjilen-1;dp[i][j]newArrayList();for(intki;kj;k){charopops.get(k);for(intl:dp[i][k]){for(intr:dp[k1][j]){if(op)dp[i][j].add(lr);elseif(op-)dp[i][j].add(l-r);elsedp[i][j].add(l*r);}}}}}returndp[0][n-1];}}复杂度时间/空间与结果规模同阶Catalan 数。关键点枚举分割点每个运算符都可能是最后一次运算遍历所有运算符作为切分点。递归基当前子串中没有运算符时说明它是单个数字直接返回该数字。记忆化同一个子表达式相同子串会被反复求解用 memo 缓存避免重复计算。结果不去重题目要求返回所有不同计算方式的结果即使数值相同也要保留例如 2-1-1 会得到两个 0。