.leetcode(300. Longest Increasing Subsequence)

문제

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

문제 풀기 전

1. rescursion으로 풀 수 있을거라 생각했다.
2. 대신 영향받는것과 가져와야될 것을 먼저 정의 해봤다. (index, number) -> count

• index는 이전까지 진행했던 index
• 이전 Index중에서 number는 가장 큰 값

직접 푼 풀이

소요시간: 30분(08:50 ~ 09:20)

class Solution {
    private int[] cache;
    public int lengthOfLIS(int[] nums) {
        cache = new int[nums.length];
        Arrays.fill(cache, -1);

        int ret = 0;
        for (int i=0; i<nums.length; i++) {
            ret = Math.max(ret, solve(nums, i)+1);
        }

        return ret;
    }

    private int solve(int[] nums, int index) {
        if (index == nums.length) {
            return 0;
        }

        if (cache[index] != -1) {
            return cache[index];
        } 

        int ret = 0;
        for (int i=index+1; i<nums.length; i++) {
            if (nums[index] < nums[i]) {
                ret = Math.max(ret, solve(nums, i) + 1);
            }
        }

        return cache[index] = ret;
    }
}

느낀점

1. 숫자를 쌓아가는 방식이라 어차피 number == nums[index] 값이기에 (index) -> count만 해결할 수 있었다.
2. dp는 끝점을 기준으로 앞에 값들을 쌓아가면서 풀었다. 아래에서 참고해 볼 수 있다.

솔루션 공부 후 추가로 푼 풀이

class Solution {

    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int[] dp = new int[nums.length];

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

        return ret;
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)

#나중에다시한번

• dp로 한번 풀어보자.
• Dynamic Programming with Binary Search방법도 있는데 다음에 풀어보자.