백준 2098번: 외판원 순회, 9251번 lcs

아이디어는 dp[i][j] : 현재 도시i , 지금까지 방문한 도시가 j인걸로 설정은 했는데 구현을 못하겠다.

 

탑다운인지 바텀업인지;; 뭐 둘다 되겠지만 구현을 둘다 못하겠다;; dfs인지 반복문으로하는게 쉬운건지도;;

 

 

 

 

9251번 

 

일단 첫 구현이 틀렸다; dp 갱신 방법을 나는 그냥 위 왼쪽 ㄳ중 큰거 가져오면 된다 했다. 근데 하다보니 에러임을 발견했다; 왜냐면 같을때 위아래에서  기록이 잘못 되서 대신 <https://kswims.tistory.com/189>

 

				 
					int tmp;
					tmp = max(dp[i - 1][j], dp[i][j - 1]);
					if (tmp > dp[i][j])
					{
						tmp++;
						if (maxv < tmp) {
							maxv = tmp;
							ans[tmp] = a[i];
							dp[i][j] = tmp;
						}
					}
				
			

이렇게 구현했는데 위와 왼쪽에서 가져온건 부분 수열이 아니다. 공통된걸로 걸려서 중복일 수도 있어서;

그니까 문제가 부분 문제를 잘 못 해결했다;;;; 

 

dp[i][j] 정의 자체도 안해놓고 풀어서 그런거 같다; 이해 못하고 가져다 써서

 

a 문자열이 i전까지 b문자열이 j전까지의 최대 공통 부분 문자열의 길이이다.