LIS(최장 증가 부분 수열) DP풀이

백준 문제를 풀다 LIS문제를 처음 마딱드렸다.
골드5문제였는데 아무리 머리를 싸매고 고민을 해봐도 해결방법이 안보여 해설을 보았더니....
DP로 푸는 방법이 있더라...

사실 DP로 풀 생각을 안한건 아니었는데 뭔가 항상 DP문제는 이차원 배열을 만들어 푸는 경우가 많아 이차원 배열로 풀려하다 너무 복잡해져서 포기했는데 알고보니 1차원 배열만 사용해도 풀렸음...

LIS - DP

public class LIS_DP {
    public static void main(String[] args) {
        int arr[] = {3, 2, 4, 1, 6};
        int dp[] = new int[arr.length];
        dp[0] = 1; // LIS의 첫 번째는 항상 1이다.
 
        for (int i = 1; i < arr.length; i++) {
            // 첫 원소부터 i원소 전까지 비교
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                //  증가 부분 수열의 길이는 1부터 시작하므로 0인 값을 1으로 변경해준다.
                if (dp[i] == 0) {
                    dp[i] = 1;
                }
            }
        }
 
        System.out.println("arr : " + Arrays.toString(arr));
        System.out.println("DP  : " + Arrays.toString(dp));
    }
}

사실 굳이 코드를 보지 않고 과정 그림만 보니깐 바로 깨달아버렸다...