Normal_11053_가장 큰 증가하는 부분 수열_코드 질문

"해당 문제에서 종료 조건이 필요 없는 것 같다!"

( 문제 링크 : http://lasai.tistory.com/28?category=687080 )

 -> 네, 맞습니다! 해당 문제는 '종료 조건' 없이도 문제의 해결이 가능합니다. 그러면 왜 필요하지 않은지에 대해 알아보도록 하겠습니다.

public static int dp(int n) {

if(n == 0)

return 0;

if(d[n] > 0)

return d[n];

for(int i = n-1; i > 0; i--) {

if(num[n] > num[i])

d[n] = Math.max(d[n], dp(i)+1);

}

return d[n];

}

 먼저, 해당 문제의 재귀 함수 부분입니다. 이를 활용하여, 다음 예제를 확인해 보겠습니다.

 문제는 증가하는 부분 수열을 구하는 것이지만, 저는 문제에 대한 접근을 반대 방향(오른쪽 -> 왼쪽)으로 진행하기 때문에 '가장 큰 감소하는 부분 수열'을 구하는 문제가 됩니다. 따라서 그림과 같이 가장 오른쪽에 있는 '4'를 먼저 선택했다 가정하겠습니다.

 다음으로, 4를 기준으로 선택될 수 있는 값들을 아래와 같이 표현할 수 있고(왼쪽 그림), 파란색과 빨간색의 과정(오른쪽 그림)이 각각 어떻게 해서 진행되었는지 확인해보겠습니다.

public static int dp(int n) { if(n == 0) return 0; if(d[n] > 0) return d[n]; for(int i = n-1; i > 0; i--) { if(num[n] > num[i]) d[n] = Math.max(d[n], dp(i)+1); } return d[n]; }

1) 파란색의 경우  - 처음 시작시, n은 값은 '4'(index)입니다. 이 데이터가 for문으로 넘어가서 '3'부터 '1'사이의 값(index)들 중, num[4]보다 작은 값을 선택하게 되는데 여기서는 '1'(index)이 선택했습니다.  - 이후, '1'(index)은 다시 재귀 함수를 타고 들어가게 되고, for문을 만나게 됩니다. 하지만 for문에서 '0'부터 '0'사이의 값(index)은 존재하지 않으므로, 해당 for문을 종료하지 않고 'd[n] = 0'을 return하게 됩니다.   - 따라서 종료 조건을 써주지 않아도 문제의 해답을 구할 수 있습니다.

 다음과 같은 이유로, 해당 문제는 '종료 조건'의 언급 없이도 답을 구할 수 있습니다.  하지만 DP 문제에 있어서, 미처 고려하지 못한 예외들이 존재할 수 있기 때문에, '종료 조건'을 먼저 구하는 것을 추천드립니다.

이상 질문 포스팅을 마치겠습니다. 감사합니다!