• 기본 개념은 wikipedia 참고
• 정확히는 최적 부분 구조(Optimal Substructure)를 지닌 중복된 하위 문제들(Overlapping Subproblems)을 분할 정복으로 풀이하는 문제해결 패러다임이다.
• 대충 답에 대한 공식을 점화식으로 표현해서 그걸 갖고 계산하면 DP라고 생각해도 별 문제 없고, 어떤 문제가 DP로 풀어야 하는 문제라는 것을 알게 되면 점화식을 세워보려고 시도하면 된다. 키워드는 '점화식'이다.

• 상향식 - bottom-up - Tabulation
• 하향식 - top-down - Memoization
• 기본적으로는 상향식이 빠르고 코드도 심플하니, 디폴트로는 상향식을 쓰는걸로 하자.
• 하향식을 쓰는게 나을때
  • 점화식의 인덱스가 자연수들로 평범하게 떨어지지 않아서 어디서부터 시작해야 할지 고민하기 복잡할때.
    • 집합이나 트리에 대한 DP등..
  • 본 문제를 푸는 데에 부분문제중 일부만이 필요할 때. 상향식은 모든 부분문제에 대한 테이블을 전부 채워가면서 올라가는데, 사실 모든 테이블을 전부 채우지 않고도 문제가 풀릴수 있는 경우
  • top down으로 푼 문제들
    • 1521.. 리프 스테이트에서부터 상위 스테이트들로 순서대로 이터레이션 시키는것이 어렵다.

• 결국 DP는 큰 범위에 대한 값을, 작은범위에 대해서 계산했던 값들을 이용해서 빠르게 계산할수 있으면 적용 가능하다. 큰 범위와 작은 범위에 해당될수 있는 것들은 다양한데, 대표적인 것들을 이런것들이다.
• [1차원 DP] - N에 대한 값을 1 ~ N-1 까지의 값들로부터 계산할 수 있는 경우
  • N-1, N-2, .., N-i 까지의 값들로만 계산할 수 있는 경우
• [2차원 DP] N,M에 대한 값을 1 ~ N-1, 1 ~ M-1 까지의 값들로 부터 계산할 수 있는 경우
• [비트마스킹을 이용한 DP] 집합에 대한 값을, 부분집합에 대한 값들로부터 계산할 수 있는 경우
• [트리에서의 DP] 트리에 대한 값을, 서브트리에 대한 값들로부터 계산할 수 있는 경우
• [위상정렬을 이용한 DP] DAG에서 현재 노드에 대한 값을, predecessor 노드들에 대한 값들로부터 계산할 수 있는 경우
• [구간 분할에 대한 DP] 구간에 대한 값을, 부분구간에 대한 값들로부터 계산할 수 있는 경우

• A(n) = f(A(n-1), A(n-2), …, A(n-k)) 인 경우
• 기본적으로 시간복잡도는 O(kn)이 된다. (k개의 인자로부터 f값을 계산하는게 O(k)라고 가정)
• 그리고, 슬라이딩 윈도우라 불리는 방법으로 공간복잡도를 O(k)에 처리할수 있다. 최근 k항의 dp값만 유지하고 나머지는 버려도 된다.
  • 하향식에서는 이 기법이 불가능하다
• 변수명을 통일하자.
  • k=1일 때에는, dp_cur과 dp_prev를 사용한다. A(n) = f(A(n-1)) 이면 dp_cur = func(dp_prev) 이렇게 업데이트하자
  • k=2일 때에는, dp_cur과 dp_prev, dp_pprev를 사용한다. A(n) = f(A(n-1)) 이면 dp_cur = func(dp_prev, dp_pprev) 이렇게 업데이트하자
  • k>=3 이상일때는 그냥 deque를 쓰자.
• 그래서 코드는 보통 이렇게 된다
  • [To be filled]

• f가 선형 함수, 즉 점화식이 dp[n] = c[1]*dp[n-1] + c[2]*dp[n-2] + … + c[k]*dp[n-k] 형태일경우, 선형 동차 점화식이라고 한다. 이 경우에는 DP로 푸는 대신, 행렬의 거듭제곱 형태로 변환하여 더 빠르게 계산 가능하다
  • 최근 k개 항으로부터 계산된다면 표현된다면, 행렬 거듭제곱으로 O(k^3*logn)에 풀수 있다. k가 큰 경우에는 키타마사법과 FFT를 버무려서 O(klogk*logn)까지 줄일수 있다
• 보통 최댓값이나 최솟값을 찾는 문제라면, f에 min이나 max가 들어가므로 해당이 안되지만, 모든 경우의 수를 찾는 문제라면 f가 선형 함수가 되어서 이 방식을 적용할 수 있는 경우가 많다.
  • 대표적으로 피보나치 함수도 이 방법으로 구할수있다.
• 자세한것은 선형 점화식 참고

• f가 인접 k항의 최솟값을 받는 함수인 경우에는, 인접 k항의 최솟값을 빠르게 구해서 전체 시간 복잡도를 줄일수 있다.
• Monotone deque 테크닉을 이용하면 인접 k항의 최솟값(또는 최댓값)을 O(k)가 아닌, amortized O(1)에 구할수 있다. 최솟값을 구한 뒤에 상수시간 처리만 필요하다면, 결국 하나의 dp값을 O(1)에 구할수 있으므로, 전체 계산은 O(n)에 할수 있다.
• 백준에서는 '덱을 이용한 다이나믹 프로그래밍' 이라고 태그되어있다
• 자세한 것은 Monotone deque 참고

• 2개의 변수에 대한 식으로 표현되는 경우. 이 경우의 구현은 2차원 배열을 채워나가는 식으로 계산하게 된다.

• 흔한 경우.
• 어떤 행에 대한 값이 이전 행에 대한 값들로 계산되는 형태
  • dp[i][j] = f(g(dp[0][0]), …, g(dp[0][N]), g(dp[1][0]), …, g(dp[1][N]), …, g(dp[i-1][0]), …, g(dp[i-1][N]))
• 대충 이렇게 된다.

  • dp = [[0] * M for _ in range(N)]
        for i in range(N):
            for j in range(M):
                dp[i][j] = some_func(dp[:i], dp[i][:j])
        
        print(dp[N - 1][M - 1])

• 인접 k항에 대한 점화식의 2차원 형태
• i번째 행에 대한 값이 i-1, i-2, …, i-k 행만 갖고 계산 가능한 상황. 이때는 N*M의 테이블을 만들 필요 없이, K*M의 테이블만으로 충분하다
• 대부분은 k=1인 경우인데, 이때는 그냥 1차원 배열만으로 된다.
• k=1 일때, 코드는 대충 이렇게 된다.

  • dp_cur = [0] * M
        for _ in range(N):
            dp_cur, dp_prev = [0] * M, dp_cur
            for i in range(M):
                for j in range(N):
                    val = update(val, func(dp_prev[j]))
                dp_cur[i] = val
        
        print(dp_cur[M - 1])

• 몇개의 셀에만 값이 채워져있고 나머지는 0으로 채워져 있는 상태에서, 값이 채워진 칸의 주변에서만 업데이트가 일어나는 형태.
• 이때는 테이블을 다 만들고 모든 셀을 iterate하는 것보다 그냥 map을 이용해서 값이 채워진 셀만 유지하는 것이 속도면에서 효율적인 경우가 있다
• 대표적인 예로는 0-1 knapsack 문제가 있다.
  • 이 문제의 BOJ 버전인 평범한 배낭에서 좀더 구체적인 예시가 설명되어있다
• 대충 코드는 이런 식이다

  • dp_cur = {0: 0}
        for i in range(N):
            dp_cur, dp_prev = dp_cur.copy(), dp_cur
            for prev_i, prev_v in dp_prev.items():
                cur_i, cur_v = func(prev_i, prev_v)
                dp_cur[cur_i] = cur_v
        
        print(dp_cur[M-1])

• 2개의 변수가 어떤 구간의 시작 인덱스와 끝 인덱스인 경우. 어떤 구간에 대한 값이 그 안에 포함된 더 짧은 구간에 대한 값들로 계산되는 형태. 말하자면 점화식이 다음처럼 생긴 형태.
  • dp[i][j] = f_k(g(dp[i][k], dp[k][j], i, k, j))
• 구간 분할 방식에 관한 DP 참고

• 어떤 집합 S에 대한 함수값이, 그 부분집합들의 값에 대한 식으로 계산되는 경우들이다.
• 전체집합의 부분집합들을 표현하는 것을 비트마스킹으로 처리하는 것은 유명한 테크닉이다. 집합을 정수형으로 표현하는 것도 가능하고, 집합과 그 부분집합간의 관계가 키값의 대소관계로 유지되는 것도 상향식 재귀를 가능하게 해준다. 하지만, 그냥 집합의 튜플 자체를 key로 잡고 재귀로 표현하는 것이 가독성에서는 오히려 나은 점도 있다보니, 아직은 그때그때 내키는대로 쓰는 중.. 어느쪽을 확정적으로 사용할지는 아직 고민중.

• n개의 원소를 배열하는 순서에 따라 값이 결정되는 함수의 최대값을 구하는 형태.
• 그냥 전부 다 해보려면 n!가지의 배열법을 다 해봐야 하지만, 남은 원소에 대한 함수값이 앞선 배치 순서에 영향을 받지 않는다면, dp[S] = max(f(x) + dp[S - x]) 와 같이 쓸 수 있고, 이것은 S의 모든 부분집합 2^|S|개에 대한 테이블을 만들고, 각각을 O(|S|)에 채우면 되므로 O(|S| * 2^|S|)로 풀수 있다.

• 링크 참고
• 이름이 거창한데, 그냥 Sum over Subsets의 약자로.. f[S] = sum(g[S - x] for x in S) 와 같은 형태로 된 f를 모든 집합에 대해서 구하는 방법이다
  • 예를 들면 f[{x,y,z}] = g[{y,z}] + g[{x,y}] + g[{y,z}] 같은 형태..
• 비트마스크로 바꿔서 생각해보면, N 이하 모든 자연수 i에 대해서, i & x = i 인 모든 x의 함수값의 합을 구하는 것과도 동일하다
• DP를 이용해서, {전체 원소의 갯수} * {집합의 갯수} 만큼의 테이블을 이용해서 O(NlogN)에 풀 수 있다 (N은 집합의 갯수). 그리고 이터레이션 순서를 잘 조절하면 공간복잡도 O(N)에 굉장히 깔끔한 코드로 정리할 수 있다. (코드는 깔끔하지만 파이썬에서의 실행속도는 매우 느리다)

• for i in range(n.bit_length() + 1):
      for num in range(n + 1):
          if num & (1 << i):
              dp[num] += dp[num ^ (1 << i)]

[To be filled]

• https://codeforces.com/blog/entry/8219
• https://koosaga.com/242