DP 연습

1. Longest Arithmetic Subsequence

문제: https://leetcode.com/problems/longest-arithmetic-subsequence/

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int ans = 1;
        int n = nums.size();
        vector<unordered_map<int, int>> dp(n);
        
        for(int i = 0; i < nums.size(); i++){
            for(int j = i + 1; j < nums.size(); j++){
                int diff = nums[i] - nums[j];
                dp[j][diff] = dp[i].find(diff) != dp[i].end() ? dp[i][diff] + 1 : 2;
                ans = max(ans, dp[j][diff]);
            }
        }
        return ans;
    }
};

 vector와 unordered_map으로 2차원 배열을 만든다.  nums[i] - nums[j]로 나오는 diff가 음수가 될 수 있으므로 이렇게 정의한다.  이중루프를 돌면서 i와 j의 차가 이전에 존재하는 경우 이전에 있던 count + 1을 해주고, 그렇지 않다면 i와 j의 값의 갯수인 2를 저장한다.

 

Time complexity: O(N^2)

Space complexity: O(N * M)

 

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int ans = 1;
        int n = nums.size();
        int dp[1001][2001];
        memset(dp, 0, sizeof(dp));
        
        for(int i = 0; i < nums.size(); i++){
            for(int j = i + 1; j < nums.size(); j++){
                int diff = nums[i] - nums[j];
                diff += 1000;
                dp[j][diff] = dp[i][diff] != 0 ? dp[i][diff] + 1 : 2;
                ans = max(ans, dp[j][diff]);
            }
        }
        return ans;
    }
};

 vector 안에 unordered_map을 넣을 수도 있고, 값의 범위가 0<= nums[i] <= 500이므로 diff의 최소값은 -1000이 된다.  이에 diff에 1000을 더해주면 모든 diff의 값이 양수가 되므로 일반 배열을 사용하여 절대 시간을 줄일 수 있다.

 

Time complexity: O(N^2)

Space complexity: O(N * M)

 

2. Longest Increasing Subsequence

문제: https://leetcode.com/problems/longest-increasing-subsequence/

Longest Increasing Subsequence - LeetCode

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

 i 위치에 있을 때 i + 1부터 nums.size()까지 루프를 돈다.  이때, nums[i] < nums[j]인 경우 longest increasing subsequence의 후보가 되므로 s[i] + 1을 s[j]에 저장한다.  만약 s[j]가 s[i]+1보다 더 큰 수가 들어오는 경우 s[j]까지 도달하는 더 긴 부분 increasing subsequence가 있는것으로 스킵한다.  

 

Time complexity: O(N^2)

Space complexity: O(N)