코드트리 - DP 유형 정리

조건에맞게 선택적으로 전진하는 DP

조건에따라 건너뛰는(점프하는) 유형을 해결하는 DP임. 전체적으로 O(N^2)의 해법으로 풀림. (dp[i]를 구하기위해 dp[:i]의 값을 모두 보고 결정하는것.)

소개 문제 : 현재 칸에 적힌 수이하로 점프가 가능. 끝까지 도착하려하는데, 최대 몇 번 점프를 할수있는지 구하기.

풀이 : 일단 dp에 해당위치까지 점프횟수를 저장하면 됨. 그럼 dp갱신방법은? 0<=j<i의 dp를 모두살펴서 갱신함. 즉. O(N^2) 방식임.

최대 증가부분수열(LIS)

문제 : 숫자가 주어졌을때, 가장 긴 증가부분수열 구하기. 1,6,4,3,9,3이 있을때 1,6,9나 1,4,9 순으로만들면 증가부분수열임 1,3,3은 33이 동일해서안됨.

풀이 : 얘도 동일하게 dp에 해당위치까지 최대 수열길이구하고, 갱신시 이전의 0<=j<i의 dp를 모두살펴서 최대값 + 1을 저장하게하면됨 (물론 seq[j]<seq[i] 여야..) 그렇게하고 max(dp)를 출력하면됨. (항상 끝 숫자를 포함한다는보장이없으므로 dp[-1]이아니라 max(dp)를 봐야함) O(N^2)

최대 감소부분수열(LDS?)

문제 : 위와 동일. 이젠 감소하는 부분수열임.

풀이 : 사실상 동일. seq[j]>seq[i]이게끔 부등호만 바꿔주면 동일하게풀림

최대 점프 횟수

문제 : 맨처음에 소개된 그문제임 끝까지갈필욘없음. 최대몇번점프가능하냐임. N<1000

풀이 : 현재 dp애서 0<=j<i 의 dp를 모두살펴서 dp[i] = max(dp[:i]) + 1 해주면 됨. 이후 max(dp)을 제출하면 됨. 다만. 가다가 점프못하게되는경우때문에 당황하였음. 즉 도중에 00000 이 있어버리면 점프가끊기니까. 이후의 dp는 사용할수가없음.

따라서 dp를 전체를 INT_MIN(음수)으로 초기화해주고, dp[0]에만 0을 줌. 그리고 dp[j]가 INT_MIN이면 점프시키지 않음. 이런 기법이 필요함.

2차원 최대증가수열

문제 : 특정룰 - 새롭게 이동하는 위치는 오른쪽으로 한칸이상, 아래로 한칸이상이어야한다. 이 예제1에서는 (1,1), (3,2), (4,4)를 가면 되므로 3 N<50

풀이 : 1차원일때랑 사실 동일한 해법으로 풀린다. 밟은 칸 수를 dp[i][j] 로 두고 (0i-1,0j-1) 범위의 서브그리드 내에서 seq[k][l] < seq[i][j]을 만족하되, dp[k][l] != INT_MIN인 경우에 dp[i][j] = max(dp[i][j], dp[k][l]+1)로 갱신전부해주면된다.

즉 한번 갱신에 O(N^2)이고, 총 N^2번갱신필요하므로 이 알고리즘은 O(N^4)

겹치지 않게 선분고르기2

문제 :

N<1000

풀이 : 여태까지와 동일하게 그냥, dp하나갱신시 이전의 dp를 전부탐색하는 방식 사용. 하려했는데 그러진못하겠다.

이번엔 이거다. dp[i]는 i번째 선분이 마지막선택선분일때 그때까지 안겹치고고른 선분의갯수임. dp 하나를 갱신하기위해 이전의 dp들을 쭉 다보는 건 맞음, 하지만 통과조건이 아주약간 바뀌었는데, x2_j < x1_i이어야함.