241. Different Ways to Add Parentheses
题目大意，给定一个数学表达式，在表达式的不同地方添加括号来表示不同的运算顺序，求最后有多少种不同的运算结果。比如给定字符串'2-1-1'，可以有两种添加括号的办法，'(2-1)-1' 和 '2-(1-1)'，结果为[0, 2]。
这个题目和word break有些类似，都是记忆化递归的题目。
本题主要的分为下面三步：
-
找到位置来分割字符串。在这里是运算符号 +, -, * . 在word break里面是预先给定的的单词。
-
对分割出来的左右两个子表达式，分别递归求解子表达式的所有的可能解。子表达式可能会重复出现，所以要用记忆体来记住已经求解过的表达式的值，这样可以节省时间。在word break II中是递归验证子表达式是不是在给定的单词集合里面。
-
对两个子表达式的值的集合，根据给定的运算符号，计算笛卡尔积
这个题目要注意的是，在递归求解子问题的时候，如果子问题中没有运算符了，比如helper('12')，应该返回'12'的整型值。否则不管怎么迭代，结果都是空集。
动态规划
class Solution:
def diffWaysToCompute(self, input):
self.res = {}
def helper(input):
n = len(input)
if input in self.res:
return self.res[input]
ans = []
for i in range(1, n):
op = input[i]
if op in ('+', '-', '*'):
left = helper(input[:i])
right = helper(input[(i+1):])
for s in left:
for k in right:
if op == "+":
ans.append(s + k)
elif op == "-":
ans.append(s - k)
elif op == "*":
ans.append(s * k)
if ans == []:
ans = [int(input)]
self.res[input] = ans
return self.res[input]
return helper(input)