a*e
2 楼
Given n pairs of parentheses, write a function to generate all combinations
of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
Recursive 的写出来了,但DP的不知道怎么做,看了别人的code也不太懂,尤其是
for(int l=0;l buff[i].push_back(buff[j][k]+"("+buff[i-j-1][l]+")");
在做啥,为啥idx要i-j-1 等完全不清楚。
另外,大家有推荐学习DP的方法么?多谢
class Solution {
public:
vector generateParenthesis(int n) {
vector res;
string r;
stack st;
dfs(res,r,0,0,n);
return res;
}
void dfs(vector &res, string r, int leftCount, int rightCount,
int n)
{
if (leftCount==n&&rightCount==n)
{
res.push_back(r);
return;
}
else
{
if (leftCount {
dfs(res,r+"(",leftCount+1,rightCount,n);
}
if (rightCount {
dfs(res,r+")",leftCount,rightCount+1,n);
}
}
}
};
class Solution {
public:
vector generateParenthesis(int n) {
vector result;
if(n<1)
return result;
vector > buff(n+1,vector());
buff[0]=vector(1,"");
for(int i=1;i<=n;i++)
{
for(int j=0;j{
for(int k=0;k for(int l=0;l buff[i].push_back(buff[j][k]+"("+buff[i-j-1][l]+")");
}
}
return buff[n];
}
};
of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
Recursive 的写出来了,但DP的不知道怎么做,看了别人的code也不太懂,尤其是
for(int l=0;l
在做啥,为啥idx要i-j-1 等完全不清楚。
另外,大家有推荐学习DP的方法么?多谢
class Solution {
public:
vector
vector
string r;
stack
dfs(res,r,0,0,n);
return res;
}
void dfs(vector
int n)
{
if (leftCount==n&&rightCount==n)
{
res.push_back(r);
return;
}
else
{
if (leftCount
dfs(res,r+"(",leftCount+1,rightCount,n);
}
if (rightCount
dfs(res,r+")",leftCount,rightCount+1,n);
}
}
}
};
class Solution {
public:
vector
vector
if(n<1)
return result;
vector
buff[0]=vector
for(int i=1;i<=n;i++)
{
for(int j=0;j{
for(int k=0;k
}
}
return buff[n];
}
};
w*a
3 楼
是DP求结果的数量么?
如果只是求数量,那就跟unqiue BST那题一样,都是卡塔兰数。
如果只是求数量,那就跟unqiue BST那题一样,都是卡塔兰数。
r*7
4 楼
这个根本不用dp,就用greedy就行了
combinations
【在 a***e 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: Given n pairs of parentheses, write a function to generate all combinations
: of well-formed parentheses.
: For example, given n = 3, a solution set is:
: "((()))", "(()())", "(())()", "()(())", "()()()"
: Recursive 的写出来了,但DP的不知道怎么做,看了别人的code也不太懂,尤其是
: for(int l=0;l : buff[i].push_back(buff[j][k]+"("+buff[i-j-1][l]+")");
: 在做啥,为啥idx要i-j-1 等完全不清楚。
: 另外,大家有推荐学习DP的方法么?多谢
: class Solution {
combinations
【在 a***e 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: Given n pairs of parentheses, write a function to generate all combinations
: of well-formed parentheses.
: For example, given n = 3, a solution set is:
: "((()))", "(()())", "(())()", "()(())", "()()()"
: Recursive 的写出来了,但DP的不知道怎么做,看了别人的code也不太懂,尤其是
: for(int l=0;l
: 在做啥,为啥idx要i-j-1 等完全不清楚。
: 另外,大家有推荐学习DP的方法么?多谢
: class Solution {
x*a
5 楼
能贴一下dp的完整代码么?
C*e
6 楼
你贴的这个解法不是DP
而且我不认为此题可以用DP做。。。
combinations
【在 a***e 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: Given n pairs of parentheses, write a function to generate all combinations
: of well-formed parentheses.
: For example, given n = 3, a solution set is:
: "((()))", "(()())", "(())()", "()(())", "()()()"
: Recursive 的写出来了,但DP的不知道怎么做,看了别人的code也不太懂,尤其是
: for(int l=0;l : buff[i].push_back(buff[j][k]+"("+buff[i-j-1][l]+")");
: 在做啥,为啥idx要i-j-1 等完全不清楚。
: 另外,大家有推荐学习DP的方法么?多谢
: class Solution {
而且我不认为此题可以用DP做。。。
combinations
【在 a***e 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: Given n pairs of parentheses, write a function to generate all combinations
: of well-formed parentheses.
: For example, given n = 3, a solution set is:
: "((()))", "(()())", "(())()", "()(())", "()()()"
: Recursive 的写出来了,但DP的不知道怎么做,看了别人的code也不太懂,尤其是
: for(int l=0;l
: 在做啥,为啥idx要i-j-1 等完全不清楚。
: 另外,大家有推荐学习DP的方法么?多谢
: class Solution {
r*3
7 楼
可以dp的, 不过LZ代码没给全吧
就是i对括号的可以这样考虑, 最左边的做括号对应的右括号有i种情况, 对于每一种情
况, 这对括号里面的j对括号已经在之前被计算过, 因为ji-j-1对括号也已经在之前被计算过, 因为i-j-1递推式
buff[i]中的元素 = '(' + buff[j]中的任意一个 + ')' + buff[i-j-1]中的任意一个
, 枚举j就行了, 0 <= j <= i-1
就是i对括号的可以这样考虑, 最左边的做括号对应的右括号有i种情况, 对于每一种情
况, 这对括号里面的j对括号已经在之前被计算过, 因为ji-j-1对括号也已经在之前被计算过, 因为i-j-1递推式
buff[i]中的元素 = '(' + buff[j]中的任意一个 + ')' + buff[i-j-1]中的任意一个
, 枚举j就行了, 0 <= j <= i-1
相关阅读
[bssd] OPT回国签证,有谁听过被拒的例子吗?请问H4,国内的CS 女PHD如何找工作谁能给几个Research Lab的工资行情(CS)cisco店面加悲剧求指点,想quit phd转master找工作今年H1B没赶上,用没批140的绿卡的EAD工作, 风险有多大?请问大家都是怎么找recruiter?学生物和化学的怎么找工作?好朋友刚刚面完G 求bless,thanks!update:被拒求分析请教有关 pre- 和 post-completion opt 使用的利弊,谢谢了!急问:H1B没赶上,能否OPT转CPT?另问达拉斯地区学校开始时间没看懂Leetcode这道题的答案,请指点firmware engineer@apple电面我打算做个类似于leetcode的网站,只用中文。很诡异的面试H1B没赶上,有人了解L1吗?诚问关于 OPT 相关的技术问题从亚马逊跳微软,有搞头没? (转载)请教: HR说