首页 > 代码库 > LeetCode中的动态规划问题（一）
LeetCode中的动态规划问题（一）
Regular Expression Matching
Problem description:
Implement regular expression matching with support for ‘.‘ and ‘*‘.
‘.‘ Matches any single character.‘*‘ Matches zero or more of the preceding element.The matching should cover the entire input string (not partial).The function prototype should be:bool isMatch(const char *s, const char *p)Some examples:isMatch("aa","a") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "a*") → trueisMatch("aa", ".*") → trueisMatch("ab", ".*") → trueisMatch("aab", "c*a*b") → true解题思路：
不是显式DP问题（保存一张表），用Recursion的思路可解。
1）若p[j+1] != ‘*‘，那么判断p[j]和s[i]的结果就可以了。
p[j]==s[i]或者p[j]==‘.‘，到当前位置是匹配的，继续向下判断；不满足条件，说明当前位置不匹配。
2）若p[j+1]==‘*‘，那么需要循环判断p[j+2]和s[i...n]是否匹配.
代码如下：
1 class Solution { 2 public: 3 bool isMatch(const char *s, const char *p) { 4 if(*p == 0) 5 return *s == 0; 6 7 if(*(p+1) != ‘*‘) 8 { 9 if(*s != 0 && (*p == *s || *p == ‘.‘))10 return isMatch(s+1, p+1);11 else12 return false;13 }14 else15 {16 while(*s != 0 && (*p == *s || *p == ‘.‘))17 {18 if(isMatch(s, p+2))19 return true;20 21 s++;22 }23 return isMatch(s, p+2);24 }25 }26 };
Longest Valid Parentheses
Problem description:
Given a string containing just the characters ‘(‘ and ‘)‘, find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
解题思路：
不是用DP解决的，用stack解决。使用pair<char, int>保存字符和位置。
1）如果s[i]==‘(‘，则压入栈；
2）如果s[i]==‘)‘，则判断st.top()是否是‘(‘，如果是则弹出栈；否则压入栈。
代码如下：
1 class Solution { 2 public: 3 int longestValidParentheses(string s) { 4 stack<pair<char,int> > st; 5 int len = s.length(); 6 7 if(len <= 1) 8 return 0; 9 10 pair<char,int> start(‘)‘,-1);11 st.push(start);12 int res = 0;13 for(int i = 0; i < len; ++i) 14 {15 if(s[i] == ‘(‘)16 {17 pair<char,int> node(s[i],i);18 st.push(node);19 }20 else21 {22 pair<char,int> top = st.top();23 if(top.first == ‘(‘)24 {25 st.pop();26 res = max(res, i-st.top().second);27 }28 else29 {30 pair<char,int> node(s[i],i);31 st.push(node);32 }33 34 }35 }36 37 return res;38 }39 };
LeetCode中的动态规划问题（一）