동적 기획의 셋째: 최장 상승 서열과 최장 공공 서열 문제

하나.최장 상승 서브시퀀스
1. 정의
LIS(i): i번째 숫자로 끝나는 최장 상승 서열의 길이를 나타냅니다.
LIS(i): [0...i]의 범위 내에서 숫자nums[i]를 선택하면 얻을 수 있는 가장 긴 상승 서열의 길이를 표시합니다
LIS(i) = max(1 + LIS(j)) (i > j)
2. 예제
300. Longest Increasing Subsequence
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note:

There may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

class Solution {
public:
    int lengthOfLIS(vector& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector memo(n+1, 1);
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    memo[i] = max(memo[i], 1 + memo[j]);
                }
            }
        }
        int res = memo[0];
        for(int i = 1; i < n; i++){
            res = max(res, memo[i]);
        }
        return res;
    }
};

둘.질문
1. 정의
두 문자열 S1과 S2를 주고 이 두 문자열의 가장 긴 공통 서열의 길이를 구하십시오
LCS(m, n)는 S1[0...m]과 S2[0...n]의 가장 긴 공통 서열의 길이이다
S1[m] == S2[n]:  LCS(m, n) = 1 + LCS(m-1, n-1)
S1[m] != S2[n]:  LCS(m, n) = max(LCS(m-1, n), LCS(m, n-1))

#include 
#include 
#include 
#include 
using namespace std;

class Solution {
public:
    int canPartition(vector& nums1,vector& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        vector > memo(m, vector(n, 0));
        if(nums1[0] == nums2[0]) memo[0][0] = 1;
        for(int i=1; i w;
    w.push_back(1);
    w.push_back(2);
    w.push_back(3);
    vector w2;
    w2.push_back(1);
    w2.push_back(2);
    w2.push_back(3);
    w2.push_back(4);
    w2.push_back(2);
    w2.push_back(3);
    int res = solution.canPartition(w, w2);
    printf("%d
",res);
    return 0;
}