一.LCS算法

1035. 不相交的线以这道题为例，明显就是一个求1143. 最长公共子序列 - 力扣（LeetCode）的题目

递推公式看代码10-15，如果需要找到所有可能得路径可以反向dfs

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        vector<vector<int>> dp(n+1,vector<int>(m+1));

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(nums1[i-1]==nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }

        int a = n;
        int b = m;

        set<vector<int>> answers;

        vector<int> s;
    
        //如果找全部反向dfs用set去重
        auto dfs = [&](auto &&dfs,int i,int j){
            if(i==0||j==0){
                answers.insert(s);
                return;
            }

            if(nums1[i-1]==nums2[j-1]){
                s.push_back(nums1[i-1]);
                dfs(dfs,i-1,j-1);
                s.pop_back();
            }else{
                if(dp[i-1][j]==dp[i][j-1]){
                    dfs(dfs,i-1,j);
                    dfs(dfs,i,j-1);
                }else if(dp[i-1][j]>dp[i][j-1]){
                    dfs(dfs,i-1,j);
                }else{
                    dfs(dfs,i,j-1);
                }
            }
        };

        dfs(dfs,n,m);

        for(auto &x:answers){
            for(auto &y:x){
                cout<<y<<" ";
            }
            cout<<endl;
        }
        //如果只找一条
        // while(a>0&&b>0){
        //     if(nums1[a-1]==nums2[b-1]){
        //         s+=to_string(nums1[a-1]);
        //         a--;
        //         b--;
        //     }else{
        //         if(dp[a-1][b]>dp[a][b-1]){
        //             a--;
        //         }else{
        //             b--;
        //         }
        //     }
        // }
        // cout<<s<<endl;


        return dp[n][m];
    }
};