What is the best pattern for Different Ways to Add Parentheses?

Use memoized divide-and-conquer over subexpressions. In dynamic programming terms, each substring is a state, and every operator inside that substring defines a transition that combines all left results with all right results.

Why is this considered dynamic programming if the solution is recursive?

The recursion defines the state transitions, but memoization is what makes it dynamic programming. Each substring or index range is solved once, and its full list of possible values is reused anywhere that state appears again.

Why do duplicate numbers stay in the output?

Because the problem asks for all possible results from all different parenthesizations, not just unique values. Two different grouping choices can evaluate to the same number, and those should both contribute to the returned list.

How do I know when a substring is a base case?

If the current piece contains no operator, it is just one integer and should return a single-element list containing that parsed value. This base case is what lets larger splits build results upward.

Can I build a bottom-up table for this problem instead of recursion?

Yes, you can tokenize numbers and operators and fill a DP table by interval length. The recurrence is the same as the recursive solution, but top-down memoization is usually shorter and easier to implement correctly for problem 241.

#241

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

为运算表达式设计优先级

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以按任意顺序返回答案。生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 10 4 。示例 1：输入： expression = "2-1-1…

数学字符串动态规划递归记忆化

题目描述

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 10⁴ 。

示例 1：

输入：expression = "2-1-1"
输出：[0,2]
解释：
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2：

输入：expression = "2*3-4*5"
输出：[-34,-14,-10,-10,10]
解释：
(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

提示：

1 <= expression.length <= 20
expression 由数字和算符 '+'、'-' 和 '*' 组成。
输入表达式中的所有整数值在范围 [0, 99]
输入表达式中的所有整数都没有前导 '-' 或 '+' 表示符号。

lightbulb

解题思路

方法一：记忆化搜索

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        @cache
        def dfs(exp):
            if exp.isdigit():
                return [int(exp)]
            ans = []
            for i, c in enumerate(exp):
                if c in '-+*':
                    left, right = dfs(exp[:i]), dfs(exp[i + 1 :])
                    for a in left:
                        for b in right:
                            if c == '-':
                                ans.append(a - b)
                            elif c == '+':
                                ans.append(a + b)
                            else:
                                ans.append(a * b)
            return ans

        return dfs(expression)

speed

复杂度分析

指标	值
时间	O(n \cdot 2^n)
空间	O(n^2 \cdot 2^n)

psychology

面试官常问的追问

外企场景

question_mark
They expect you to say each operator can be the final operation, which defines the subproblem split.
question_mark
They want memoization once you notice the same substring is evaluated from multiple recursive branches.
question_mark
They may check whether you preserve duplicate results, because different parenthesizations can yield the same value.

warning

常见陷阱

外企场景

error
Evaluating with normal arithmetic precedence instead of generating every parenthesization misses valid outputs like the alternate result in "2-1-1".
error
Returning a set instead of a list incorrectly removes duplicates, which breaks cases like "2 _3-4_ 5" where -10 appears twice.
error
Memoizing only one number per substring is wrong because each subexpression in Different Ways to Add Parentheses can produce many values.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the number of distinct results instead of the full result list, which changes storage but keeps the same split pattern.
arrow_right_alt
Support additional operators such as division, where you must define integer behavior and guard invalid splits like divide-by-zero.
arrow_right_alt
Solve the same recurrence with index-based DP over tokens instead of substring slicing to reduce string handling overhead.

help

常见问题

外企场景

继续练习

#224 基本计算器 #140 单词拆分 II #139 单词拆分