citizen   2달 전

dp[n][m] 은 n번째 숫자부터 m번째 숫자까지 이어지는 부분 수열 내의 가장 긴 증가하는 수열의 길이이며

max[n][m]은 위에서 말한 가장 긴 증가하는 수열에서 가장 큰 값을 나타냅니다.

dp[n][n] = 1, max[n][n] = n+1번째 숫자로 초기 세팅을 해주고

i = a-1부터 시작해서(즉 맨 뒤에서부터 거꾸로)

N+1번째 숫자가 max[i][n-1]보다 크면 기존의 증가하는 수열에 포함시킬 수 있으므로

dp[i][n] = dp[i][n-1]+1, max[i][n] = N+1번째 숫자가 되도록 하고

만약 max[i][n-1]보다 작으면 기존에 구한 증가수열의 부분수열 중(k = i+1부터 시작해서)

dp값이 가장 큰 것을 dp[i][n]로 정했습니다.(만약 해당 부분수열의 max값이 N+1번째 숫자보다 작으면 +1을 해주었습니다)


어디서 잘못된 걸까요?


sgchoi5   2달 전

DP[i] 는 0, 1, 2, 3 ... i 의 최대 부분 증가 수열의 개수

for (int i = 0; i < N; i++) {
        DP[i] = 1; // 처음에는 나 혼자로 시작
        for (int j = 0; j < i; j++) {
            if (A[i] > A[j] && DP[i] < DP[j] + 1)
                DP[i] = DP[j] + 1; // 이전 모든 가장 긴 부분 수열에서 하나를 더하는 경우

        }

    }

끝나면 DP 안에서 제일 큰 값을 찾으면 됩니다

citizen   2달 전

제가 놓친 부분을 알았습니다. 

N번째 값(마지막)을 포함하지 않는 경우에도 최대값이 나올 수 있군요.

조언 감사합니다

댓글을 작성하려면 로그인해야 합니다.