0

对于给定的 n 找到有效括号的有效组合的数量。我告诉他加泰罗尼亚数的直接公式（因为我之前遇到过这个问题）但他特别想要这个问题使用动态编程的解决方案，并想要带有测试用例解释的工作解决方案。我没有设法找到有效的解决方案。

例如：

n=1 有效面值=0

n=2 有效面值=1

现在我只想了解这个问题

我找到了一种解释，但没有得到它请您帮助我理解，或者您能否提供对以下逻辑的更详细的解释（这似乎是正确的）

你需要偶数个括号，如果 C(n) 用 2 * n 括号表示有效括号的数量，那么

C(0)=1 and for any n>0

C(n)=C(0) * C(n-1)+C(1) * C(n-2)+...+C(n-1) * C(0)=sum(i=0,n-1,C(i) * C(n-1-i))

因为您需要以 '(' 开头并查看带有 ')' 的右括号在哪里，如果它们之间有 2 * i 括号，那么这种情况的数量是C(i) * C(n-1-i).

4

2 回答 2

1

M[i][j] dp 状态。i - j 之间的长度总是偶数。

那么问题类似于矩阵乘法。

M[i][j] = M[i][i+1]*M[i+2][j] + M[i][i+3]*M[i+4][j] + .. ... + M[i][j-2]*M[j-1][j]

还要添加第 i 个括号是 '(' 并且第 j 个括号是 ')' 的情况

M[i][j] += M[i+1][j-1]

于 2020-07-29T09:12:47.967 回答
1

递归是这里的关键。

将 N 分为 N/2 和 N/2（开括号和闭括号的计数）。

选择开括号，将其添加到结果字符串中，并减少其计数并进行递归调用。

选择右括号，将其添加到结果字符串中，并减少其计数并进行递归调用。

要仅打印有效括号，请确保在任何给定时间点，右括号计数不小于开括号计数，因为这意味着右括号已与其各自的开括号一起打印。

看看这个链接。

于 2020-07-27T12:23:51.430 回答