括号生成问题（leetcode 22）
思路：
- 确定使用递归
- 确定递归剪枝条件：
- 当左括号left大于n时，非法，剪枝
- 当右括号right比左括号left多时，非法，剪枝
- 对于获得排列组合题，构建集合，递归函数带上路径path
- 路径就加个左括号，left就++，加个右括号right就++
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = set()
self.dfs(n, 0, 0, "", res)
return list(res)
def dfs(self, n, left, right, path, res):
if left > n or right > left:
return
if len(path) == n * 2:
res.add(path)
return
self.dfs(n, left+1, right, path+"(", res)
self.dfs(n, left, right+1, path+")", res)
最长有效括号（leetcode 32）
妈呀，这是我在面试华为的时候，出的一道题。
当时用栈做出来了，现在试试DP，逆天的DP，脑子不够用了
DP思路：
- 先对s进行基本的修正，左边为
)的不可能匹配成功，右边为(不能匹配成功，直接strip掉 - 边界条件返回0
- 构建dp，dp[0]肯定为0，从1开始遍历
- 判断s[i]为
(的情况，匹配失败dp[i] = 0 - 判断s[i]为
)的情况:- 如果 i >= 1 并且 s[i-1] == "("，匹配成功，如果 i == 1, dp[i-2] -> dp[-1] == 0
i == 0 or s[i-1] == ")"的情况，i==0时，dp[0]=0，不管； 剩下s[i-1] == ")"的情况，注意i - dp[i-1] > 0即确定与s[i]对应的"("存在，且为"("，即可得出dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]
举个栗子🌰："()(())"，i指向5时，dp[i-dp[i-1]-2] -> dp[5-2-2] == dp[1] == 2，"(())"，i指向3时，dp[i-dp[i-1]-2] -> dp[-1] == 0
PS: dp[i-dp[i-1]-2]在这种情况下，可能存在也可能不存在，不存在则为 dp[-1] = 0，没有赋值就是0，存在就直接加
class Solution:
def longestValidParentheses(self, s: str) -> int:
s = s.lstrip(")").rstrip("(")
if len(s) == 0:
return 0
dp = [0 for _ in range(len(s))]
for i in range(1, len(s)):
# if s[i] == '(': dp[i] = 0 # 以(结尾非法，dp初始化就为0，可以省略
if s[i] == ')': # 如果为右括号，左边匹配成功且i>=2，dp依赖
if i >= 1 and s[i-1] == '(':
dp[i] = dp[i-2] + 2
else: # 如果匹配不成功，i - dp[i-1]为s[i]的左括号位置（如果有的话）
if i - dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(':
dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]
return max(dp)
再次强调：第二题DP仅用于锻炼DP能力，本题最优解还是用栈比较好