DP (Dynamic Programming)

• DP Condition
  1. Optimal Substructure

     큰문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를해결 한다.

  2. Overlapping Subproblem

     동일한 작은 문제를 반복적으로 해결해야 한다.

• 점화식 (Recurrence relation) : 인접한 항들 사이의 관계식

• DP테이블: 메모이제이션에 사용된 리스트

• 푸는순서
  1. 상태 정의
     • dp(i,j) –> i 와 j 관계 정의
     • 초기상태 정의
  2. get 점화식 (모든걸 포함한 점화식이 될수도, 짝수나 홀수 등 특정 조건에 맞는 점화식이 될수도 있음)
  3. 시간복잡도 계산
     • 재귀로 풀지 반복문으로 풀지 판단하기 위함  모든 재귀는 while로 만들 수 있음 (훨씬 빠름)
  4. 코딩
• 푸는 방법
  1. Top-Down (재귀) –>Pypy3 활용 : Memoization: 한번 계산한 결과 메모리에 메모 (Caching 이라고도 함)
  2. Bottom-Up (반복) –> 파이썬 : DP 의 전형적인 형태
• 문제 유형
  • 2d 배열 관계 문제
  • 입력 A 와 DP 동일 사이즈 초기에 만들어줌
  • 사이즈는 왼쪽에 0 깔아두는게 좋아서 N+1 하면 좋음
  • 점화식 생각 잘 해야함. 주석으로 DP 식을 써두는 습관
  • DP[i][j] : i, j 도착했을때 최댓값

  • DP[i][j] = max(DP[i-1][j-1], DP[i-1][j]) + A[i][j]

  • LIS: 가장 큰 부분 수열 (오르막 내리막 유형)

  • 2차원 배열의 합 -> 누적합
    • 1차원배열 누적합
      • DP[i] = i 까지 합
      • i 부터 j 까지의 합은 DP[j] – DP[i-1]
    • 2차원배열 누적합 (C++로 푸는걸 추천)
      • 대각선(왼위)가 중복계산되어 처리 필요
      • DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + A[i-1][j-1]
      • (i, j) ~ (x, y) 의 합: DP[x][y] - DP[i-1][y] - DP[x][j-1] + DP[i-1][j-1]
• DP VS divide & conquer
  • Both usable if Optimal Substructure
  • DP have Overlapping Subproblem but div & conquer do not overlap