[리트코드] 300. Longest Increasing Subsequence - js (DP)

1. 문제

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

Longest Increasing Subsequence - LeetCode

2. 코드

정답 but 타임아웃)

DFS를 사용하여 푼 코드이다. 정답이지만 nums의 길이가 길면 타임아웃이 뜬다. 아무래도..for 문 때문에 실행되어야 할 로직이 무지 길어지겠지..

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let candidate = [];

    const dfs = (left,before,count) => {
        candidate.push(count);
        
        for(let i=0;i<left.length;i++){
            if(before < left[i]){
                let newLeft = left.slice(i+1);
                let newCount = count + 1;
                dfs(newLeft,left[i],newCount);
            }
        }
    }

    for(let i=0;i<nums.length;i++){
        let newNums = nums.slice(i);
        dfs(newNums,nums[i],1);
    }

    return Math.max(...candidate);
};

정답)

DP를 사용하면 시간 복잡도를 줄일 수 있다. 또 DP냐!! 내가 제일 어려워하는..

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    const n = nums.length;
    if (n === 0) return 0;

    const dp = new Array(n).fill(1); // 각 인덱스에서 시작하는 LIS의 길이를 저장하는 배열

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

    return Math.max(...dp);
};