[LeetCode] 300. Longest Increasing Subsequence - 동적계획법(Dynamic Programming) + DFS(깊이우선탐색) + LIS(최장증가부분수열) JAVA

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

코드설명

동적계획법(Dynamic Programming) + DFS(깊이우선탐색) + LIS(최장증가부분수열) 을 활용합니다.

 

이 문제는 유명한 LIS 문제입니다. 

동적계획법을 활용하여 중복계산을 피하여 시간복잡도는 O(n)입니다.

코드

class Solution {
    int[] nums;
    int[] memo;
    public int lengthOfLIS(int[] nums) {
        this.nums = nums;
        memo = new int[nums.length + 1];
        Arrays.fill(memo, -1);
        return DFS(-1) - 1;
    }

    int DFS(int idx){
        int ret = 1;
        if(idx == -1){
            for(int i = idx + 1; i < this.nums.length; i++){
                ret = Math.max(ret, DFS(i) + 1);
            }
            return memo[idx + 1] = ret;
        }

        if(memo[idx + 1] != -1) return memo[idx + 1];

        ret = 1;
        for(int i = idx + 1; i < this.nums.length; i++){
            if(this.nums[idx] < this.nums[i])
                ret = Math.max(ret, DFS(i) + 1);
        }
        return memo[idx + 1] = ret;
    }
}