Uncrossed Lines Solutions in C++

/// Source : https://leetcode.com/problems/uncrossed-lines/
/// Author : liuyubobobo
/// Time   : 2019-04-27

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


/// Memory Search
/// Time Complexity: O(|A| * |B|)
/// Space Complexity: O(|A| * |B|)
class Solution {
public:
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {

        unordered_map<int, vector<int>> Apos, Bpos;
        for(int i = 0; i < A.size(); i ++)
            Apos[A[i]].push_back(i);
        for(int i = 0; i < B.size(); i ++)
            Bpos[B[i]].push_back(i);

        vector<vector<int>> dp(A.size(), vector<int>(B.size(), -1));
        return dfs(A, B, 0, 0, Apos, Bpos, dp);
    }

private:
    int dfs(const vector<int>& A, const vector<int>& B, int ai, int bj,
            unordered_map<int, vector<int>>& Apos,
            unordered_map<int, vector<int>>& Bpos,
            vector<vector<int>>& dp){

        if(ai >= A.size() || bj >= B.size())
            return 0;

        if(dp[ai][bj] != -1) return dp[ai][bj];

        int res = dfs(A, B, ai + 1, bj, Apos, Bpos, dp);
        for(int j: Bpos[A[ai]])
            if(j >= bj)
                res = max(res, 1 + dfs(A, B, ai + 1, j + 1, Apos, Bpos, dp));

        return dp[ai][bj] = res;
    }
};


int main() {

    vector<int> A1 = {3};
    vector<int> B1 = {3, 3, 2};
    cout << Solution().maxUncrossedLines(A1, B1) << endl;
    // 1

    return 0;
}

/// Source : https://leetcode.com/problems/uncrossed-lines/
/// Author : liuyubobobo
/// Time   : 2019-04-30

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


/// Memory Search
/// It's actualy The Longest Common Subsequence Problem
///
/// Time Complexity: O(|A| * |B|)
/// Space Complexity: O(|A| * |B|)
class Solution {
public:
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {

        vector<vector<int>> dp(A.size(), vector<int>(B.size(), -1));
        return dfs(A, B, 0, 0, dp);
    }

private:
    int dfs(const vector<int>& A, const vector<int>& B, int ai, int bj,
            vector<vector<int>>& dp){

        if(ai >= A.size() || bj >= B.size())
            return 0;

        if(dp[ai][bj] != -1) return dp[ai][bj];

        int res = dfs(A, B, ai + 1, bj, dp);
        for(int j = bj; j < B.size(); j ++)
            if(A[ai] == B[j])
                res = max(res, 1 + dfs(A, B, ai + 1, j + 1, dp));

        return dp[ai][bj] = res;
    }
};


int main() {

    vector<int> A1 = {3};
    vector<int> B1 = {3, 3, 2};
    cout << Solution().maxUncrossedLines(A1, B1) << endl;
    // 1

    vector<int> A2 = {2, 5, 1, 2, 5};
    vector<int> B2 = {10, 5, 2, 1, 5, 2};
    cout << Solution().maxUncrossedLines(A2, B2) << endl;
    // 3

    return 0;
}

/// Source : https://leetcode.com/problems/uncrossed-lines/
/// Author : liuyubobobo
/// Time   : 2019-04-30

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


/// Dynamic Programming
/// It's actualy The Longest Common Subsequence Problem
/// 2-D Dynamic Programming
///
/// Time Complexity: O(|A| * |B|)
/// Space Complexity: O(|A| * |B|)
class Solution {
public:
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {

        vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
        for(int i = 1; i <= A.size(); i ++)
            for(int j = 1; j <= B.size(); j ++)
                dp[i][j] = max(max(dp[i - 1][j], dp[i][j - 1]), (A[i - 1] == B[j - 1]) + dp[i - 1][j - 1]);

//        for(int i = 0; i <= A.size(); i ++){
//            for(int j = 0; j <= B.size(); j ++)
//                cout << dp[i][j] << " ";
//            cout << endl;
//        }

        return dp[A.size()][B.size()];
    }
};


int main() {

    vector<int> A1 = {3};
    vector<int> B1 = {3, 3, 2};
    cout << Solution().maxUncrossedLines(A1, B1) << endl;
    // 1

    vector<int> A2 = {2, 5, 1, 2, 5};
    vector<int> B2 = {10, 5, 2, 1, 5, 2};
    cout << Solution().maxUncrossedLines(A2, B2) << endl;
    // 3

    vector<int> A3 = {1, 4, 2};
    vector<int> B3 = {1, 2, 4};
    cout << Solution().maxUncrossedLines(A3, B3) << endl;
    // 2

    return 0;
}

/// Source : https://leetcode.com/problems/uncrossed-lines/
/// Author : liuyubobobo
/// Time   : 2019-04-30

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


/// Dynamic Programming
/// It's actualy The Longest Common Subsequence Problem
/// 1-D Dynamic Programming
///
/// Time Complexity: O(|A| * |B|)
/// Space Complexity: O(|B|)
class Solution {
public:
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {

        vector<int> dp(B.size() + 1, 0);
        for(int i = 1; i <= A.size(); i ++){
            for(int j = B.size(); j >= 1; j --)
                if(A[i - 1] == B[j - 1])
                    dp[j] = 1 + dp[j - 1];
            for(int j = 1; j <= B.size(); j ++)
                dp[j] = max(dp[j], dp[j - 1]);
        }

        return dp[B.size()];
    }
};


int main() {

    vector<int> A1 = {3};
    vector<int> B1 = {3, 3, 2};
    cout << Solution().maxUncrossedLines(A1, B1) << endl;
    // 1

    vector<int> A2 = {2, 5, 1, 2, 5};
    vector<int> B2 = {10, 5, 2, 1, 5, 2};
    cout << Solution().maxUncrossedLines(A2, B2) << endl;
    // 3

    vector<int> A3 = {1, 4, 2};
    vector<int> B3 = {1, 2, 4};
    cout << Solution().maxUncrossedLines(A3, B3) << endl;
    // 2

    return 0;
}