# Double sequence DP

`//without optimizationclass 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];            }};`

## 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

--

--

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.