다이나믹 프로그래밍 (LCS 2)

개수를 구하는 코드는 LCS1 문제에 있으므로 그 부분은 생략한다.

 

다른 사람의 풀이를 보고 내 방식 대로 풀었다. 다른 사람의 풀이를 보지 않았다면 못 풀었을 것 같다.

역 추적으로 구하는 방식인데 아래 그림처럼 처음으로 숫자가 +1 되었을 때를 기준으로 문자열을 저장했다.

 

처음으로 +1이 되었다는것을 판별 할 때는 아래와 같은 규칙이 있다.

1. 자기 자신의 위나 왼쪽 중에 같은 숫자가 있다면 인덱스를 그 위치로 바꾼다.

2. 자기 자신의 위나 왼쪽 중에 더이상 같은 숫자가 없다면 대각선에 위치한 인덱스로 위치를 바꾼다.

3. 대각선으로 위치를 바꾸기 직전의 인덱스가 처음으로 +1이 된 위치다.

 

DP의 값이 0 이되면 추적을 멈춘다.