有多少种不同的表达方式可能？

Question

我遇到了以下练习题.

您可以随意将任何括号放在表达式中,也可以根据需要添加任何括号.但是,在放入括号后,它应该是一个有效的表达式.问题是你可以制作多少个不同的数字？防爆.因为1 - 2 + 3 - 4 - 5你可以得到六个独特的价值如下:

1 - 2 + 3 - 4 - 5 = -7 

1 - (2 + 3) - 4 - 5 = -13

1 - (2 + 3 - 4) - 5 = -5

1 - (2 + 3 - 4 - 5) = 5

1 - 2 + 3 - (4 - 5) = 3

1 - (2 + 3) - (4 - 5) = -3

我似乎无法弄清楚如何为这个问题制定动态编程方案.我刚开始解决涉及动态编程的问题,似乎无法弄清楚如何解决这个问题.

编辑数字范围是0 <= N <= 100和表达长度(<= 30)

Answer 1

基本思路

括号基本上插在数字和运算符之间，任何不平衡都可以在整个表达式的末尾修复。

括号的可能位置

紧邻任一运算符之前的A(都是非法语法。

(紧跟在 a 之后的A+是合法的，但毫无意义，因为它不会改变求值的顺序。我假设我们不这样做。

(紧跟在 a 之后的A-是合法且重要的。

)紧接在 a 之前的A+是合法且重要的，前提是之前有匹配项(。

)紧接在 a 之前的A-是合法的，但毫无意义，因为在后面的数字后面打开一对新的括号会给出相同的符号更改，并且稍后会提供更多选项，因为我们将有一个可以闭合的多对开放括号。我假设我们也不会这样做。

这意味着我们实际需要的唯一括号是负数之前的左括号和正数之后的右括号。如果我们坚持这两个，则求和中下一个数字相乘的符号仅取决于左括号的数量是偶数还是奇数。

这给了我们

下部结构

从左到右解析状态，在每个数字之后，当前的子问题可以表示为一组

• 部分总和和
• 左括号的数量。

制定具体示例

阅读+1：

(1, 0)

也就是说，这个子问题只有一个解决方案：到目前为止，部分和为 1，左括号的数量为 0。从现在开始，在每个子问题中，我将用一行来表示每个子问题产生的对。前一个子问题中的配对。

阅读-2：

(-1, 1), (-1, 0)

即部分和为-1，但我们可能插入也可能没有插入左括号。

阅读+3：

(-4,1),(-4,0)

(2,0)

这个子问题的新增内容：我们可以选择关闭一对括号，但前提是其中一个括号是开着的。

阅读-4：

(0,2), (0,1)

(-8,0), (-8,1)

(-2,0), (-2,1)

阅读-5：

(-5,2), (-5,3)

(5,1), (5,2)

(-13,0), (-13, 1)

(-3,1), (-3,2)

(-7,0), (-7,1)

(3,1), (3,2)

最后，我们通过仅查看每对的第一个元素并丢弃重复项来获得可能的总和。