题目如下：

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are+, - and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34((2*3)-(4*5)) = -14((2*(3-4))*5) = -10(2*((3-4)*5)) = -10(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

解法：

这道题首先想到的是采用递归的分治方法解，但这种方法明显存在大量子问题重复计算的情况。单用递归实现最终运行时间只打败了16%的提交结果，考虑到性能的优化，于是采用动态规划的方法重新实现一遍，采用一个hashmap记录已经算出的子问题结果，在遇到已经算出结果的子问题时直接从hashmap中get到计算结果。需要引入一个helper函数，将该hashmap作为实参传入helper函数，随着helper函数的递归不断向hashmap中加入新的子问题结果。

public class Solution {    public List
     
       diffWaysToCompute(String input) {        Map
      
       > memory = new HashMap
       
        >();        return helper(input, memory);    }    public List
        
          helper(String input, Map
         
          > memory) {        List
          
            rst = new LinkedList
           
            (); int len = input.length(); for (int i = 0; i < len; i++) { if (input.charAt(i) == '+' || input.charAt(i) == '-' || input.charAt(i) == '*') { String s1 = input.substring(0, i); String s2 = input.substring(i + 1, len); List
            
              p1 = memory.get(s1); List
             
               p2 = memory.get(s2); if (p1 == null) { p1 = helper(s1, memory); } if (p2 == null) { p2 = helper(s2, memory); } for (int m: p1) { for (int n: p2) { switch (input.charAt(i)) { case '+': rst.add(m + n); break; case '-': rst.add(m - n); break; case '*': rst.add(m * n); break; default: break; } } } } } if (rst.size() == 0) { rst.add(Integer.valueOf(input)); } memory.put(input, rst); return rst; }}
             
            
           
          
         
        
       
      
     

采用动态规划的方法，最终运行时间打败了88.56%的提交结果，大大提高了运行速度。