[LeetCode] 300. Longest Increasing Subsequence

300. Longest Increasing Subsequence

LeetCode

 

Given an integer array nums, return the length of the longest strictly increasing subsequence.

정수 배열 nums가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 반환하세요.

 

Example

Input: nums = [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.

Input: nums = [0,1,0,3,2,3]
Output: 4

Input: nums = [7,7,7,7,7,7,7]
Output: 1

---

1. 문제 요구사항 분석

증가하는 숫자의 길이 반환

연속하는 숫자가 아니라 배열 순서를 지키면서 무조건 증가하도록 만들기

[0, 1, 0, 3, 2, 3]의 경우, 0 - 1 - 2 - 3

 

2. 접근 전략

😭 DFS + 가지치기로 구현하기: 시간복잡도 O(2^n) → Time Limit Exceeded 23 / 56 testcases passed

import java.util.*;

class Solution {
    int answer = 0;

    public int lengthOfLIS(int[] nums) {
        dfs(nums, 0, Integer.MIN_VALUE, 0);
        return answer;
    }

    public void dfs(int[] nums, int start, int prev, int length) {
        answer = Math.max(answer, length);

        for (int i = start; i < nums.length; i++) {
            if (nums[i] > prev) {
                dfs(nums, i + 1, nums[i], length + 1);
            }
        }
    }
}

 

😭 DFS + 메모이제이션: 시간복잡도 O(n^2) 

메모이제이션: 동일한 계산을 반복해야 할 때, 이전에 계산한 결과값을 메모리에 저장해 두었다가 재사용하여 실행 속도를 높이는 최적화 기법

앞에서 이미 계산한 값을 이용하기 !!

import java.util.*;

class Solution {
    int[] nums;
    int[] memo;

    public int lengthOfLIS(int[] nums) {
        this.nums = nums;
        memo = new int[nums.length];

        int answer = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {
            answer = Math.max(answer, dfs(i));
        }

        return answer;
    }

    public int dfs(int cur) {
        if (memo[cur] != 0) {
            return memo[cur];
        }

        memo[cur] = 1; // 자기 자신

        // i 이전에 작은 값의 갯수 계산
        for (int i = 0; i < cur; i++) {
            if (nums[i] < nums[cur]) {
                memo[cur] = Math.max(memo[cur], memo[i] + 1);
            }
        }

        return memo[cur];
    }
}

 

😁 DP로 풀기 (dfs + 메모이제이션보다 간단해짐): 시간복잡도 O(n^2) 

import java.util.*;

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];

        int answer = 0;

        for (int i = 0; i < n; i++) {
            dp[i] = 1; // nums[i] 하나만 고르는 경우

            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            answer = Math.max(answer, dp[i]);
        }

        return answer;
    }
}