1. 子序列（不连续）
1.2 LeetCode第1143题—最长公共子序列（583题使用到了这一题）
LeetCode题目链接:
https://leetcode-cn.com/problems/longest-common-subsequence/
- 解题思路：这道题最难思考的地方在于当s[i-1] != t[j-1] 的时候，这个递推公式应该怎样去思考
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
//既然知道了相同子序列如何来做，那么最大如何来做呢？
int m = text1.size(),n = text2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(int i = 1;i<=m;++i)
{
for(int j = 1;j<=n;++j)
{
if(text1[i-1] == text2[j-1])
//相同的公共序列
dp[i][j] = dp[i-1][j-1] + 1;
else
//不相等，就说明此时t中的这个字符在s中是没有的，那么应该删除
//然后对于这一步递推公式应该怎样思考呢？
//可以思考为"abc" -> "ace" 最后一位是不相同的
dp[i][j] = std::max(dp[i][j-1],dp[i-1][j]);
}
}
return dp[m][n];
}
};
1.2 LeetCode第300题—最长递增子序列
LeetCode题目链接：
https://leetcode-cn.com/problems/longest-increasing-subsequence/
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
//dp[i]表示以下标i为结尾的递增子序列长度
//为啥初始化的时候要给1，因为非一个元素都是独立的一个递增子序列
vector<int> dp(nums.size(),1);
for(int i = 1;i<nums.size();++i)
{
for(int j = 0;j<i;++j)
{
if(nums[j] < nums[i])
dp[i] = std::max(dp[i],dp[j]+1);
}
}
//并不一定数组最后一个元素才是最长的递增子序列
int maxlong = 0;
for(int i = 0;i<nums.size();++i)
{
maxlong = std::max(maxlong,dp[i]);
}
return maxlong;
}
};
1.3 LeetCode第1035题—不相交的线
LeetCode题目链接:
https://leetcode-cn.com/problems/uncrossed-lines/
解题思路：直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。所以
本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度
！求最长的公共子序列长度的时候使用的是字符串，这里就只需要将字符串修改为数组就可以了。(
求最长的公共子数组
)
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(),n = nums2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
//其实这道题就是变相的求最长的公共子序列的题
for(int i =1;i<= m;i++)
{
for(int j = 1;j<=n;j++)
{
if(nums1[i-1] == nums2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = std::max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n];
}
};
2. 子序列（连续）
2.1 LeetCode第674题—最长连续递增序列
LeetCode题目链接:
https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
//你会发现你最开始的做题思路就是最长连续递增序列的思路
//dp[i] 表示数组下标i的最长且连续递增的子序列
vector<int> dp(nums.size(),1);
for(int i = 1;i<nums.size();++i)
{
if(nums[i-1] < nums[i])
dp[i] = dp[i-1] + 1;
}
int maxlong = 0;
for(int& e : dp)
{
maxlong = std::max(maxlong,e);
}
return maxlong;
}
};
2.2 LeetCode第718题—最长重复子数组
LeetCode题目链接:
https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
子序列默认不连续，子数组默认连续
class Solution {
public:
//我就觉得很奇怪，从哪里感觉出来的这个题目要归结到连续的这一类中
//子序列默认不连续，子数组默认连续
int findLength(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(),n = nums2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
int result = 0;
for(int i =1;i<=m;i++)
{
for(int j = 1;j<=n;j++)
{
//只有在两个相等的时候才会考虑跟新这个dp[i][j]
if(nums1[i-1] == nums2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
result = std::max(result,dp[i][j]);
}
}
return result;
}
};
2.3 LeetCode第53题—最大连续子序和
LeetCode题目链接:
https://leetcode-cn.com/problems/maximum-subarray/
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.empty())
return 0;
int sum = nums[0];
int max = nums[0];
for(int i = 1;i<nums.size();++i)
{
//如果前一段提供的是正向的，那么加上此时的数，毋庸置疑是会变大的
//但是如果前面的数本身都是负的了，那么给nums[i]所提供的帮助就将会是负的，会变的更小
sum = std::max(sum + nums[i],nums[i]);
if(sum > max)
max = sum;
}
return max;
}
};
3. 编辑距离
3.1 LeetCode第392题—判断子序列
LeetCode题目链接:
https://leetcode-cn.com/problems/is-subsequence/
-
解题思路：双指针法
这道题是可以使用双指针进行解答的，这里只是提供一种解题思路
class Solution {
public:
//判断s是否是t的子序列
//双指针法
//也可以使用动态规划的方法，但是如何做呢，需要好好思考一下，这是编辑距离的一类问题
bool isSubsequence(string s, string t) {
int n = s.size(),m = t.size();
int i = 0,j = 0;
while(i < n && j < m)
{
if(s[i] == t[j])
i++;
j++;
}
return i == n;
}
};
②动态规划方法
本题和最长公共子序列有很多的相似之处这算是编辑距离一类题型中比较简单的了。
首先就是状态的定义，dp[i][j] 表示，s的前i个字符和t的前j个字符的相同子序列长度
class Solution {
public:
//也可以使用动态规划的方法，但是如何做呢，需要好好思考一下，这是编辑距离的一类问题
//这道题算是编辑距离简单的题型了
//dp[i][j] 表示，s的前i个字符和t的前j个字符的相同子序列长度
bool isSubsequence(string s, string t) {
int m = s.size(),n = t.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(int i = 1;i<=m;++i)
{
for(int j = 1;j<=n;++j)
{
if(s[i-1] == t[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
//不相等，就说明此时t中的这个字符在s中是没有的，那么应该删除
dp[i][j] = dp[i][j-1];
}
}
return dp[m][n] == s.size();
}
};
3.2 LeetCode第115题—不同的子序列
LeetCode题目链接:
https://leetcode-cn.com/problems/distinct-subsequences/
dp[i][j]表示的是，s的前i个字符的子序列和t的前j个字符的相同数量为dp[i][j]
“bagg” —-> “bag” 当s[3] == s[2]的时候，此时就需要考虑两种情况，一种就是不使用这个s[3],一种就是使用这个s[3],具体就参考上面
-
难点
：这里
class Solution {
public:
//这道题的思考路线按理来说应该就是编辑距离的思路，但是我发现转变过来还是不太容易
//s中子序列和t相同的个数
//dp[i][j] s的前i个字符子序列和t的前j个字符相同的个数
//但是这道题为什么要使用uint64_t这个还需要好好的进行思考
int numDistinct(string s, string t) {
int m = s.size(),n = t.size();
//为什么要将里面的类型换成uint64_t这个类型呢
vector<vector<uint64_t>> dp(m+1,vector<uint64_t>(n+1,0));
//此时还需要进行初始化的工作
for(int i = 0;i<= m;++i)
{
dp[i][0] = 1;
}
for(int j = 1;j<= n;++j)
{
dp[0][j] = 0;
}
for(int i = 1;i<= m;++i)
{
for(int j = 1;j<= n;++j)
{
//这道题的示例其实很有意思
//"bagg" -> "bag"
// g -> g相同
//此时分为了两种情况：一种就是使用这个s[i-1]这个g，一种就是不使用这个g
//不使用：dp[i-1][j]
//使用：
if(s[i-1] == t[j-1])
//如果使用int这里很有可能会大数溢出，所以这里还需要进行修改
dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
else
//因为你是要用左边的字符串完全的去匹配右边的字符串
//"rabbb" -> "rabbi" 最后一个字符是不相等的
dp[i][j] = dp[i-1][j];
}
}
return dp[m][n];
}
};
3.3 LeetCode第583题—两个字符串的删除操作
LeetCode题目链接:
https://leetcode-cn.com/problems/delete-operation-for-two-strings/
-
解题思路：①
为了使删除操作的次数最少，剩下的字符应尽可能多。当剩下的字符为两个字符串的最长公共子序列时，删除操作的次数最少
。因此，可以计算两个字符串的最长公共子序列的长度，
然后分别计算两个字符串的长度和最长公共子序列的长度之差，即为两个字符串分别需要删除的字符数，两个字符串各自需要删除的字符数之和即为最少的删除操作的总次数
。所以这道题的解题思路，首先就是找到最长的公共子序列。
class Solution {
public:
//根据示例，两边都能修改
int minDistance(string word1, string word2) {
//dp[i][j] 表示word1的前i个字符和word2的前j个字符相同的最小步数
//下面的代码就是求最长的公共子序列的代码
//因为要让步数足够少，那么序列就要足够长，这样才能够得到最少的步数
int m = word1.size(),n = word2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(int i = 1;i<=m;++i)
{
for(int j = 1;j<=n;++j)
{
if(word1[i-1] == word2[j-1])
//相同的公共序列
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = std::max(dp[i][j-1],dp[i-1][j]);
}
}
int lcs = dp[m][n];//(最长公共子序列)
return (m+n)-2*lcs;//这一步就是求word1要到lcs的最小步数 + word2要到lcs的最小步数，然后就能让他们都到达lcs
}
};
-
解题思路：②
动态规划解法
首先我们就是要进行状态的定义，
dp[i][j] 表示word1的前i个字符和word2的前j个字符想要达到相等，所需要删除元素的最少次数
class Solution {
public:
//dp[i][j] 表示word1的前i个字符和word2的前j个字符想要达到相等，所需要删除元素的最少次数
int minDistance(string word1, string word2) {
int m = word1.size(),n = word2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
//对于第一行第一列的初始化
for(int i = 0;i<=m;++i)
dp[i][0] = i;
for(int j = 0;j<=n;++j)
dp[0][j] = j;
for(int i = 1;i<=m;++i)
{
for(int j = 1;j<=n;++j)
{
if(word1[i-1] == word2[j-1])
dp[i][j] = dp[i-1][j-1]; //因为这一步是不用走的
else
//此时有三种可能，要么删除word1[i-1]
//要么删除word2[j-1]
//两个不相同的字符同时删除，那么操作的次数就会+2
dp[i][j] = std::min(std::min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+2);
}
}
return dp[m][n];
}
};
3.4 LeetCode第72题—编辑距离(重点)
链接:
https://leetcode-cn.com/problems/edit-distance/
class Solution {
public:
//这种题首先一拿到之后应该怎么思考都是一个问题？
//这道题最少的步数我们是可以算出来的，但是最多的步数是算不出来的，因为或许很大很大
//对于这道题来说，我们可能会在推导递推公式的时候不明白怎么推导，但是如果我们使用案例去推导，就会简单很多
//对于这道题最好的理解，就是我们首先画一个图，然后我们填写dp的表格
//增加：("a" -> "ab") dp[i][j] = dp[i][j-1] + 1;
//删除：("ab" -> "a") dp[i][j] = dp[i-1][j] + 1;
//修改：("ab" -> "ac") dp[i][j] = dp[i-1][j-1] + 1;（后面的+1，就是具体的操作增删改其中的一步）
//而且我们一定要多开辟一行一列，这样做的目的就是为了，因为word1为空字符串或者word2为空字符串的情况
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
//此时应该进行初始化 比如说word1"" -> "abcd"，那么就全是增加
for(int i = 0;i<=n;++i)
{
dp[0][i] = i;
}
//word1是"abcd" -> "" 此时就全部都是删除的操作
for(int j = 0;j<= m;++j)
{
dp[j][0] = j;
}
for(int i = 1;i<= m;++i)
{
for(int j = 1;j<= n;++j)
{
if(word1[i-1] == word2[j-1])
dp[i][j] = dp[i-1][j-1];
else
//此时就是不相等，那么就要在增删改中找到步数最少的哪一个
dp[i][j] = 1 + std::min(dp[i][j-1],std::min(dp[i-1][j],dp[i-1][j-1]));
}
}
return dp[m][n]; //返回的是最少的修改步数
}
};
3.5 LeetCode第44题—通配符匹配(重点)
LeetCode题目链接：
https://leetcode.cn/problems/wildcard-matching/
dp[i][j] 表示字符串s的前i个字符和字符串前j个字符是否能进行匹配，所以里面都是bool值
以”abcd”和“ab*”来画图
但是这道题其实在初始化的哪里，有一个地方是很容易忽略的，因为*可以匹配空串，所以对于第一行的初始化的时候，如果一开始就是字符 “ * ”,那么他就可以和空串匹配，如果连续有多个，那么都可以匹配，但是这个“ * ”是不能在中间位置出现的。
比如：“***a” 那么前三个初始位置都可以初始化为True，但是如果是“a * *b”，那么初始化都是false
class Solution {
public:
//dp[i][j] 表示字符串 s 的前 i 个字符和模式 p 的前 j 个字符是否能匹配
bool isMatch(string s, string p) {
int m = s.size(),n = p.size();
//这里开辟空间其实有点类似于求最长的公共子序列 和 编辑距离这题，为社么要多开辟一行呢？
//那是因为要考虑道空串的问题
vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
//这里还有一个情况也是需要考虑的,也就是初始化的时候
dp[0][0] = true;
//这里的情况初始化也就是模式串一开始就是*，并且有可能是优很多个
//abcd ***a; 正确的特殊情况 abcd a*b* 错误的特殊情况，一旦不在开头，直接跳出，不做任何修改
for(int i = 1;i<=n;++i)
{
if(p[i-1] == '*')
dp[0][i] = true;
else
break;
}
for(int i = 1;i<=m;++i)
{
for(int j = 1;j<=n;++j)
{
if(s[i-1] == p[j-1] || p[j-1] == '?')
{
dp[i][j] = dp[i-1][j-1];
}
else if(p[j-1] == '*')
{
//abcd ab*来画图
dp[i][j] = dp[i-1][j] || dp[i][j-1];
}
}
}
return dp[m][n];
}
};
4. 回文
回文子串是要连续的，回文子序列可不是连续的
，这句话也是做题解题思考的关键点
4.1 LeetCode第647题—回文子串
LeetCode题目链接：
https://leetcode-cn.com/problems/palindromic-substrings/
解题思路：
回文子串这道题所使用动态规划定义的状态其实是很特殊的一种设定方法。
dp[i][j] : 表示字符串s在[i,j]区间的子串是否是一个回文串
难点：①为啥要倒着遍历（那是因为当求dp[i][j]的时候，首先得知道dp[i+1][j-1]）②
class Solution {
public:
//这道题采用的动态规划的方法是和平时不一样的
//返回的是回文子串的数目
//状态定义：dp[i][j]表示的是[i,j]区间字符串是否是回文子串
//对于这个开辟的二位数组来说，画图的话一定是
// a b c
// a
// b
// c
int countSubstrings(string s) {
vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
int result = 0;
//这里首先要解释清楚的就是为什么这里在倒着遍历
//是因为我们要是想要求得dp[i][j] 那么我们需要dp[i+1][j-1]的状态，所以需要倒着遍历来推
for(int i = s.size()-1;i>= 0;i--)
{
//并且i>j的情况是不用考虑的，所以直接跳过去，这里也就是在画一个二维数组的右半三角
for(int j = i;j< s.size();++j)
{
if(s[i] == s[j])
{
//说明这是独立字符
//还有就是"aa"的情况
if(j-i<=1)
{
result++;
dp[i][j] = true;
}
else if(dp[i+1][j-1])
{
result++;
dp[i][j] = true;
}
}
}
}
return result;
}
};
解法2：因为你会发现这道题使用动态规划并不是很好理解，所以我们改用另外的方法。
中心扩散法
,大师我突然又觉得好像第一种动态规划的方法也不是很难理解了。
class Solution {
public:
int Extend(string& s,int left,int right)
{
int count = 0;
while(left>=0 && right < s.size() && s[left] == s[right])
{
left--;
right++;
count++;
}
return count;
}
int countSubstrings(string s) {
//每一个元素都可以作为回文的中心点，但是这个中心点有可能是1个，也有可能是两个
int result = 0;
for(int i = 0;i<s.size();++i)
{
result += Extend(s,i,i); //奇数个 比如“aba”
result += Extend(s,i,i+1);//偶数个 比如“abba”
}
return result;
}
};
4.2 LeetCode第5题—最长回文子串
LeetCode题目链接：
https://leetcode-cn.com/problems/longest-palindromic-substring/
动态规划的解法其实就是在回文子串的基础上我们算了找到了那个最长的回文子串，并且将其从字符串中将其截取出来。
class Solution {
public:
//对于回文子串这道题，我们能够找到所有的回文子串，然后再来找里面最长的当然也是可以的
//但是这里还有一种方法就是，中心扩散法，做这道题会更加的容易
//这道题使用动态规划的写法是可以使用到回文子串的写法的
string longestPalindrome(string s) {
vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
int maxlength = 1;
int begin = 0;
//这里首先要解释清楚的就是为什么这里在倒着遍历
//是因为我们要是想要求得dp[i][j] 那么我们需要dp[i+1][j-1]的状态，所以需要倒着遍历来推
for(int i = s.size()-1;i>= 0;i--)
{
//并且i>j的情况是不用考虑的，所以直接跳过去，这里也就是在画一个二维数组的右半三角
for(int j = i;j< s.size();++j)
{
if(s[i] == s[j])
{
//说明这是独立字符
//还有就是"aa"的情况
if(j-i<=1)
{
dp[i][j] = true;
}
else if(dp[i+1][j-1])
{
dp[i][j] = true;
}
}
//这里就会得到所有的回文子串，然后我们再来比较一下，哪一个回文子串是最大的
//上面是找到了区间所有的[i,j]的回文子串，这里就是并判断一下这个回文子串的长度
//这一步就需要好好想想，当然中心扩散法也是要会的
if(dp[i][j] == true && j-i+1 > maxlength)
{
maxlength = j-i+1;
begin = i;
}
}
}
string str = s.substr(begin,maxlength); //我他妈也是服自己了，咱们咋可能会写一个i在这里呢？
return str;
}
};
4.3 LeetCode第516题—最长回文子序列
LeetCode题目链接：
https://leetcode-cn.com/problems/longest-palindromic-subsequence/
解题思路：
-
解法1动态规划解法：
class Solution {
public:
//dp[i][j]表示从区间[i,j]的最长回文字符串子序列的长度
//dp[i][j] 表示s的第 i 个字符到第j个字符组成的子串中，最长的回文序列长度是多少
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n,vector<int>(n,0));
//这个是在初始化对角线的部分
for(int i = 0;i<n;++i)
{
dp[i][i] = 1;
}
//必须要倒着遍历，因为只有倒着遍历才能用上别的状态变化
for(int i = n-1;i>=0;i--)
{
for(int j = i+1;j<n;++j)
{
if(s[i] == s[j])
//[i+1,j-1]区间的回文子串+2
dp[i][j] = dp[i+1][j-1] + 2;
else
dp[i][j] = std::max(dp[i+1][j],dp[i][j-1]);
}
}
return dp[0][n-1];
}
};
解法2：这道题其实是有一个很容易和原来题联系在一起的方式的，那就是将字符串反转，然后找两个字符串的最长公共子序列的问题。
class Solution {
public:
string Reverse(string s)
{
int left = 0,right = s.size()-1;
while(left < right)
{
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
return s;
}
int longestCommonSubsequence(string& s,string& str)
{
int m = s.size();
int n = str.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(int i = 1;i<=m;++i)
{
for(int j = 1;j<=n;++j)
{
if(s[i-1] == str[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = std::max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n];
}
//人家有个想法简直就太nb了
//将s逆转一下，然后求两个字符串的最长公共子序列的长度就可以了
int longestPalindromeSubseq(string s) {
string str = Reverse(s);
return longestCommonSubsequence(s,str);
}
};
4.4 LeetCode第132题—分割回文串II
LeetCode题目链接：
https://leetcode-cn.com/problems/palindrome-partitioning-ii/
解题思路：
①首先这道题使用到了回文子串的解题，这样我们就得到了所有的回文子串
②dp[i]:范围是[0, i]的回文子串，最少分割次数是dp[i]
③dp[j]表示的是将[0,i]区间使用j来进行切分，那么dp[j]表示的就是以j为下标，并将前j个字符切割为回文子串的最少次数，现在如果[j+1,i]区间也是回文串了，那么就是在dp[j]的基础上在+1，就是此时[0,i]的最少切割次数，是得前i个字符都是回文串的结果。
class Solution {
public:
//这道题其实就是回文子串和最长回文子串两道题相结合的题目
//先使用回文子串的解题的方法记录下所有的回文子串
int minCut(string s) {
//这一段代码就是回文子串的代码
vector<vector<bool>> isplindarome(s.size(),vector<bool>(s.size(),false));
for(int i = s.size()-1;i>=0;i--)
{
for(int j = i;j<s.size();++j)
{
if(s[i] == s[j])
{
if(j-i<= 1 || isplindarome[i+1][j-1])
isplindarome[i][j] = true;
}
}
}
//这个表示从[0,i]区间的最小分割次数
vector<int> dp(s.size(),INT_MAX);
dp[0] = 0;//就一个字符的时候，分割的次数肯定是0，此时并不能在继续分割了
for(int i = 1;i<s.size();++i)
{
if(isplindarome[0][i])
{
//说明这一段已经是回文串了,就不需要在继续分割了
dp[i] = 0;
continue;
}
for(int j = 0;j<i;++j)
{
//从j开始切割，然后如果[j+1,i]也是回文串
if(isplindarome[j+1][i])
dp[i] = std::min(dp[i],dp[j]+1);
}
}
return dp[s.size()-1];
}
};
5. LeetCode第647题—乘积最大子数组
LeetCode题目链接：
https://leetcode-cn.com/problems/maximum-product-subarray/
这道题来维护两个数组，分别存储以数组下标i为结尾的最大值和最小值的乘积数组
class Solution {
public:
//子数组必须是连续的，从测试用例也能够感受出来
int maxProduct(vector<int>& nums) {
//分别维护一个最大值和最小值的数组
//这样初始化最大的好处就是，不用初始化Maxdp[0]和Mindp[0];
vector<int> Maxdp(nums),Mindp(nums);
for(int i = 1;i<nums.size();++i)
{
if(nums[i] >= 0)
{
Maxdp[i] = std::max(nums[i],Maxdp[i-1]*nums[i]);
Mindp[i] = std::min(nums[i],Mindp[i-1]*nums[i]);
}
else
{
//此时nums[i]<0，那么前一个的最小值*当前这个nums[i]就变成了最大值
//那么前一个的最大值*当前这个nums[i]就变成了最小值
Maxdp[i] = std::max(nums[i],Mindp[i-1]*nums[i]);
Mindp[i] = std::min(nums[i],Maxdp[i-1]*nums[i]);
}
}
int Max = Maxdp[0];
for(int i = 1;i<nums.size();++i)
{
Max = std::max(Max,Maxdp[i]);
}
return Max;
}
};
6. LeetCode第10题—正则表达式匹配
class Solution {
public:
//p能否完全的表达s，这就是这道题的关键
bool isMatch(string s, string p) {
int m=s.size(),n=p.size();
vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
dp[0][0]=true; //为啥要开始的时候初始化位true
for (int j = 1; j <= p.size(); j++)
{
if (p[j-1] == '*')
dp[0][j] = dp[0][j-2];
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(s[i-1]==p[j-1] || p[j-1]=='.'){
dp[i][j]=dp[i-1][j-1];
}
else if(p[j-1]=='*'){
if(s[i-1]!=p[j-2] && p[j-2]!='.')
dp[i][j]=dp[i][j-2];
else{
//如果p的*前边字符和s当前字符相等或者p的字符是‘.'
//三种可能
//匹配0个，比如aa aaa*也就是没有*和*之前的字符也可以匹配上（在你（a*）没来之前我们(aa)已经能匹配上了）dp[i][j]=dp[i][j-2](匹配0个就相当于删除*前面那个字符)
//匹配1个，比如aab aab* 也就是*和*之前一个字符只匹配s串的当前一个字符就不看*号了 即 dp[i][j]=dp[i][j-1]
//匹配多个，比如aabb aab* b*匹配了bb两个b 那么看aab 和aab*是否能匹配上就行了，即dp[i][j]=dp[i-1][j]
//（这里这个匹配多个始终有一些理解不了）
dp[i][j]=dp[i][j-2] || dp[i][j-1] || dp[i-1][j];
}
}
}
}
return dp[m][n];
}
};