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
相关阅读
OPT STEM即将到期，春节回国纠结中全球经济衰退开始了，硅谷裁员大势所趋今天发奖金的时候，整个人都偷头里吓可住了【内部推荐】2016 德勤 Deloitte 内部推荐uber就是一个血汗工厂Chubby Dick Emporium请问大家senior 的title会显示在offer letter里吗你们这些傻逼们真诚找个男朋友找工作能帮忙就帮忙，喜欢BSO的就让他们BSO有H1b， 但是离开美国回中国工作超过一年，之后还能申请H1b 去美国吗？在FLAG混到中层比去uber这样的强多了求内推苹果老码农 谷歌team match求收留senior machine learning scientists needed at appleG家，请问这样的面试表现拿到offer的几率如何？OPT挂靠有帮忙申请H1B的吗Udacity Nanodegree 与FLAG 合作。 找不到工作退钱求offer比较Drop*box or Uwalmart关269店, 雷万员 (转载)