백준 11722번 - 가장 긴 감소하는 부분 수열 (Java)

https://www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

코드 :

dp - topdown

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int dp[];
    static int seq[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        dp = new int[N+1];
        seq = new int[N+1];

        //입력 수열 초기화
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }
        dp[1] = 1;
        for (int i = 1; i <= N; i++) {
            recur(i);
        }
        int max = 0;
        for (int i = 1; i <= N; i++) {
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);

    }

    public static int recur(int N){
        if(dp[N] == 0){
            dp[N] = 1;

            for (int i  = N - 1; i >= 1; i--) {
                if(seq[N] < seq[i]){
                    dp[N] = Math.max(recur(i) + 1, dp[N]);
                }
            }

        }

        return dp[N];
    }
}

https://programming-beard.tistory.com/130 전에 풀었던 문제와 동일한 내용이다. 다시 푸니 헷갈리기도 하고, 풀었던 문제임에도 탑다운 바텀업을 자유롭게 오가지 못한다. 공부하고 정리할 코드가 많다는 걸 느꼈다.