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
在做啥，为啥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
}
}
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 的大作中提到】
: 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 {
combinations
【在 a***e 的大作中提到】
: 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 的大作中提到】
: 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 {
而且我不认为此题可以用DP做。。。
combinations
【在 a***e 的大作中提到】
: 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
相关阅读
T家股票现在值多少？Jr. software developer Referral1G内存读10G文件知道 电话面试官 是一个中国人。 ？除了版上频繁讨论的FLAG等大公司，还能投哪？做码农好累请教一个函数默认返回值的问题，纠结很久了H1B在extension pending情况下,可以transfer吗？统计5年经验，expected salary 一般要多少啊？出师不利的面试VMware vs OracleF家电话一面请教OPT挂靠请问单耳聋算disability么？share一点面经关于leetcode上那个买卖股票II的问题qualcomm需要绿卡办export license吗? (转载)Referral: Senior System Engineer转行找码工的话，公司会不会联系phd老板Interleave Strings那个题目有O(n)时间 O(1)空间算法么？