算法专题：线性DP

参考练习习题总集

10. 正则表达式匹配

第一道题就是困难题让我很难蚌。真是磨人啊。

class Solution {
public:bool isMatch(string s, string p) {int * * matrix=new int * [p.size()+1];for (int i=0;i<p.size()+1;i++){matrix[i]=new int [s.size()+1];for (int j=0;j<s.size()+1;j++)matrix[i][j]=0;}matrix[0][0]=1;for (int i=1;i<p.size();i+=2){if (p[i]=='*') matrix[i+1][0]=1;else break;}for (int i=1;i<p.size()+1;i++)for (int j=1;j<s.size()+1;j++)if (s[j-1]==p[i-1] or p[i-1]=='.'){if (matrix[i-1][j-1]==1){matrix[i][j]=1;}}else if (p[i-1]=='*'){if (matrix[i-2][j]==1){matrix[i][j]=1;continue;}if (matrix[i][j-1]==1 and (s[j-1]==p[i-2] or p[i-2]=='.'))matrix[i][j]=1;}bool result=matrix[p.size()][s.size()];for (int i=0;i<p.size()+1;i++)delete [] matrix[i];return result;}
};

44. 通配符匹配

嗨嗨嗨，思想差不多的，又水一道困难题。

class Solution {
public:bool isMatch(string s, string p) {int len1=s.size(),len2=p.size();int * * matrix=new int * [len2+1];for (int i=0;i<len2+1;i++){matrix[i]=new int [len1+1];for (int j=0;j<len1+1;j++)matrix[i][j]=0;}matrix[0][0]=1;for (int i=0;i<len2;i++)if (p[i]=='*') matrix[i+1][0]=1;else break;for (int i=1;i<len2+1;i++)for (int j=1;j<len1+1;j++){if (s[j-1]==p[i-1] or p[i-1]=='?'){if (matrix[i-1][j-1]==1)matrix[i][j]=1;}else if (p[i-1]=='*'){if (matrix[i-1][j]==1){matrix[i][j]=1;continue;}if (matrix[i-1][j-1]==1 or matrix[i][j-1]==1)matrix[i][j]=1;}}bool result=matrix[len2][len1];for (int i=0;i<len2+1;i++)delete [] matrix[i];return result;}
};

45. 跳跃游戏

记忆化搜索。这里的记忆化搜索本质就是线性DP。做这道题时真是气死我了，一开始明明记着长度为0的时候需要特判，但是后面做着做着就忘了加上去，交了一次又发现if (temp[i]!=0) return temp[i];没有加上去，连着犯了两次低级错误。

class Solution {
public:vector<int> lb;vector<int> temp;int jump(vector<int>& nums) {if (nums.size()==1) return 0;lb=nums;temp.resize(nums.size(),0);return dfs(0);}int dfs(int i){if (temp[i]!=0) return temp[i];if (i+lb[i]>=lb.size()-1) return 1;int result=1e4-1;for (int j=lb[i];j>=1;j--){int result_temp=dfs(i+j)+1;if (result_temp<result)result=result_temp;}temp[i]=result;return result;}
};

53. 最大子数组和

前缀和。

class Solution {
public:int maxSubArray(vector<int>& nums) {int * lb=new int [nums.size()+1];lb[0]=0;for (int i=1;i<nums.size()+1;i++)lb[i]=lb[i-1]+nums[i-1];int min_value=0,result=INT_MIN;for (int i=1;i<nums.size()+1;i++){int result_temp=lb[i]-min_value;if (result_temp>result) result=result_temp;if (lb[i]<min_value) min_value=lb[i];}delete [] lb;return result;}
};

线性DP。

class Solution {
public:int maxSubArray(vector<int>& nums) {for (int i=1;i<nums.size();i++)if (nums[i-1]>0)nums[i]+=nums[i-1];int result=INT_MIN;for (int i=0;i<nums.size();i++)if (nums[i]>result)result=nums[i];return result;}
};

91. 解码方法

class Solution {
public:int numDecodings(string s) {if (s[0]=='0') return 0;int * lb=new int [s.size()+1];lb[0]=0;lb[1]=1;for (int i=2;i<s.size()+1;i++)if (s[i-1]=='0'){if (s[i-2]=='1' or s[i-2]=='2')lb[i]=max(lb[i-2],1);else return 0;}else{lb[i]=lb[i-1];if (s[i-2]=='1' or (s[i-2]=='2' and s[i-1]<='6'))lb[i]+=max(lb[i-2],1);}int result=lb[s.size()];delete [] lb;return result;}
};

97. 交错字符串

记忆化搜索。

class Solution {
public:string string1,string2,string3;vector<vector<int>> temp;bool isInterleave(string s1, string s2, string s3) {if (s1.size()+s2.size()!=s3.size()) return false;string1=s1;string2=s2;string3=s3;temp.resize(s1.size()+1,vector<int> (s2.size()+1,0));return func(0,0);}bool func(int l1,int l2){if (l1==string1.size() and l2==string2.size()) return true;if (temp[l1][l2]!=0) return temp[l1][l2]==1;bool result=false;if (l1<string1.size() and string1[l1]==string3[l1+l2])result|=func(l1+1,l2);if (l2<string2.size() and string2[l2]==string3[l1+l2])result|=func(l1,l2+1);temp[l1][l2]=result?1:-1;return result;}
};

线性DP。

class Solution {
public:bool isInterleave(string s1, string s2, string s3) {if (s1.size()+s2.size()!=s3.size()) return false;int * * matrix=new int * [s1.size()+1];for (int i=0;i<s1.size()+1;i++){matrix[i]=new int [s2.size()+1];for (int j=0;j<s2.size()+1;j++)matrix[i][j]=0;}queue<pair<int,int>> dl;dl.push(make_pair(0,0));while (1){queue<pair<int,int>> temp;if (dl.front().first+1<=s1.size())temp.push(make_pair(dl.front().first+1,dl.front().second));while (!dl.empty()){int x=dl.front().first,y=dl.front().second;if (x==0 and y==0) matrix[x][y]=1;else if (x==0){if (matrix[x][y-1]==1 and s2[y-1]==s3[y-1])matrix[x][y]=1;}else if (y==0){if (matrix[x-1][y]==1 and s1[x-1]==s3[x-1])matrix[x][y]=1;}else{if ((matrix[x][y-1]==1 and s2[y-1]==s3[x+y-1]) or (matrix[x-1][y]==1 and s1[x-1]==s3[x+y-1]))matrix[x][y]=1;}if (dl.front().second+1<=s2.size())temp.push(make_pair(dl.front().first,dl.front().second+1));dl.pop();}if (temp.empty()) break;dl=temp;}bool result=matrix[s1.size()][s2.size()];for (int i=0;i<s1.size()+1;i++)delete [] matrix[i];return result;}
};

115. 不同的子序列

wtql，感觉神功大成。

class Solution {
public:int numDistinct(string s, string t) {int mod=1e9+7;int * * matrix=new int * [s.size()+1];for (int i=0;i<s.size()+1;i++){matrix[i]=new int [t.size()+1];for (int j=0;j<t.size()+1;j++)matrix[i][j]=0;}for (int i=1;i<s.size()+1;i++)for (int j=1;j<t.size()+1;j++)if (s[i-1]==t[j-1]){matrix[i][j]=(matrix[i][j]+matrix[i-1][j])%mod;matrix[i][j]=(matrix[i][j]+matrix[i-1][j-1])%mod;if (j==1) matrix[i][j]+=1;}else matrix[i][j]=matrix[i-1][j];int result=matrix[s.size()][t.size()];for (int i=0;i<s.size()+1;i++)delete [] matrix[i];return result%mod;}
};

119. 杨辉三角II

简单题！！！

class Solution {
public:vector<int> getRow(int rowIndex) {vector<vector<int>> lb={{1}};for (int i=1;i<=rowIndex;i++){vector<int> temp;temp.push_back(1);for (int j=1;j<i;j++)temp.push_back(lb[i-1][j-1]+lb[i-1][j]);temp.push_back(1);lb.push_back(temp);}return lb[rowIndex];}
};

LCR 161. 连续天数的最高销售额

前缀和。

class Solution {
public:int maxSales(vector<int>& sales) {int * lb=new int [sales.size()+1];lb[0]=0;for (int i=1;i<sales.size()+1;i++)lb[i]=lb[i-1]+sales[i-1];int min_value=0,result=INT_MIN;for (int i=1;i<sales.size()+1;i++){int result_temp=lb[i]-min_value;if (result_temp>result) result=result_temp;if (lb[i]<min_value) min_value=lb[i];}delete [] lb;return result;}
};

线性DP。
和53. 最大子数组和一样。
虽然做每道题的时间可能会有点久，但是再也不像以前那样完全没有办法了，那就这样吧。