Double sequence DP

//without optimization
class Solution {
public:
bool isMatch(string s, string p) {
const int m = s.length(), n = p.length();
s = "#" + s;
p = "#" + p;
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
dp[0][0] = 1;
//dp[0][x]
for(int j=1;j<=n;++j)
{
if(p[j]=='*')dp[0][j] = dp[0][j-1];
}
//dp[x][0], no needed to update.
for (int i=1;i<=m;++i)
{
for(int j=1;j<=n;++j)
{
if (p[j]=='?')
{
dp[i][j] = dp[i-1][j-1];
}
else if (p[j] == '*')
{
for (int k=0;k<=i;++k)
{
dp[i][j] |= dp[i-k][j-1];
}
}
else if(p[j]==s[i])dp[i][j] = dp[i-1][j-1];
}
}
return dp[m][n];

}
};
class Solution {
public:
bool isMatch(string s, string p) {
const int m = s.length(), n = p.length();
s = "#" + s;
p = "#" + p;
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
dp[0][0] = 1;
//dp[0][x]
for(int j=1;j<=n;++j)
{
if(p[j]=='*')dp[0][j] = dp[0][j-1];
}
//dp[x][0], no needed to update.
for (int i=1;i<=m;++i)
{
for(int j=1;j<=n;++j)
{
if (p[j]=='?')
{
dp[i][j] = dp[i-1][j-1];
}
else if (p[j] == '*')
{
dp[i][j] = dp[i][j-1] || dp[i-1][j];
}
else if(p[j]==s[i])dp[i][j] = dp[i-1][j-1];
}
}
return dp[m][n];

}
};

321. Create Maximum Number

Put everything inside the loops (TLE)

class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int K) {
const int m = nums1.size(), n = nums2.size();
nums1.insert(nums1.begin(), 0);
nums2.insert(nums2.begin(), 0);
string dp[m+1][n+1][K+1];

for (int i=0;i<=m;++i)
for (int j=0;j<=n;++j)
for (int k=1;k<=min(i+j, K);++k)
{
dp[i][j][k] = "";
if(i>0)dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-1]+to_string(nums1[i]));
if(j>0)dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1]+to_string(nums2[j]));
if(i>0)dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]);
if(j>0)dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]);
}
vector<int> ret;
for (auto c:dp[m][n][K])
{
ret.push_back(c-'0');
}
return ret;
}
};
  • 包含i,
  • 不包含i,
  • 包含j,
  • 不包含j。
[5,2,2][6,4,1]3
  • 结尾为2的情况为: 52, 62,
  • 结尾不为2的情况为: 56, 26 ,65
  • 结尾为6的情况为: 56, 26
  • 结尾不为6 的情况为:52,62, 65
  • 结尾为2的情况,
  • 结尾不为2的情况(包含结尾为6的情况, 及单独去除2不用的情况)
  • 结尾为6的情况,
  • 结尾不为6的情况(包含结尾为2的情况,及单独去除6不用的情况) —
  • 结尾为2的情况
  • 单独去除2不用的情况
  • 结尾为6的情况
  • 单独去除6不用的情况
class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int K) {
const int m = nums1.size(), n = nums2.size();
nums1.insert(nums1.begin(), 0);
nums2.insert(nums2.begin(), 0);
string dp[m+1][n+1][K+1];
for (int j=1;j<=n;++j)
for(int k=1;k<=min(j, K);++k)
{
dp[0][j][k] = max(dp[0][j-1][k], dp[0][j-1][k-1]+to_string(nums2[j]));
}

for (int i=1;i<=m;++i)
for(int k=1;k<=min(i, K);++k)
{
dp[i][0][k] = max(dp[i-1][0][k], dp[i-1][0][k-1]+to_string(nums1[i]));
}

for (int i=1;i<=m;++i)
for (int j=1;j<=n;++j)
for (int k=1;k<=min(i+j, K);++k)
{
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-1]+to_string(nums1[i]));
dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1]+to_string(nums2[j]));
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]);
dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]);
//dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k]);
}
vector<int> ret;
for (auto c:dp[m][n][K])
ret.push_back(c-'0');
return ret;
}
};
class Solution {
public:
deque<int> get_max(vector<int>& nums, int k){
int remain = nums.size() - k;
deque<int> ret;
for (int i=0; i<nums.size();++i)
{
while(remain && ret.size()>0 && nums[i]>ret.back())
{
remain--;
ret.pop_back();
}
ret.push_back(nums[i]);
}
ret.resize(k);
return ret;
}

vector<int> merge(deque<int> p1, deque<int> p2){
const int K = p1.size() + p2.size();
vector<int> ret;
for(int i=0;i<K;++i)
{
if(p2>p1)
{
ret.push_back(p2.front());
p2.pop_front();
}
else
{
ret.push_back(p1.front());
p1.pop_front();
}
}
return ret;

}

vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int K) {
const int m = nums1.size(), n = nums2.size();
vector<int> ret;
for (int i=0;i<=K;++i)
{
if (i>m) break;
if (K-i>n) continue;
deque<int> p1 = get_max(nums1, i);
deque<int> p2 = get_max(nums2, K-i);
vector<int> temp = merge(p1, p2);
ret = max(ret, temp);
}
return ret;
}
};

Reference

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store