DP

• DP 문제 풀이 조건
  • 최적 부분 구조, 최적 하위 구조 (Optimal Substructure)
    • 크기가 n인 문제에서, 문제 해결 형태는 같지만 n 미만의 원소를 가지는, 더 작은 크기의 문제의 풀이법을 사용하는 것이 최적의 풀이법에 해당하면 이를 optimal substructure
      • 크기가 n인 문제에서 k < n인 k의 비슷한 문제의 관점에서 정의한다는 뜻, 더 작은 원소에 대한 최적의 풀이법을 찾고, 이들을 결합해서 최종 풀이법 완성
      • 문제를 풀기 위한 최적의 해가, 그 하위 문제들의 최적해를 이용해 구성될 수 있을 때
    • 피보나치
      • F(n) = F(n-1) + F(n-2)
    • 하위 문제의 답을 조합하여 상위 문제의 답이 됨
  • 중복 부분 문제, 하위 문제의 반복 계산 (Overlapping Subproblems)
    • 큰 문제를 풀기 위해 동일한 작은 문제를 반복해서 계산해야 할 때
    • 작은 문제를 단 한번만 풀자
      • 메모이제이션, 타뷸레이션
    • 피보나치
      • F(5) → F(4) + F(3)
      • F(4) → F(3) + F(2)
      • F(3) → F(2) + F(1)
      • 중복되는 연산이 있는 경우
• DP 적용 체크 리스트
  • 문제를 같은 형태의 하위 문제로 나눌 수 있는가
    • 하위 문제들의 해결로 상위 문제를 해결할 수 있는가
  • 하위 문제의 계산이 반복되는가
  • 최적화, 최대화, 최소화나 어떤 작업의 경우의 수를 구하는 유형의 문제인가
• 풀이 순서
  1. DP 적용할 수 있는지 확인
  2. 점화식 또는 재귀 과정 정의
     1. 문제를 하위 문제를 사용해 하향식으로 정의
     2. 맨 아래에 해당하는 ‘기본 경우’에 대한 답을 정의
     3. 종료 조건 추가
  3. 메모 전략을 시도
  4. 상향식으로 문제 풀이에 도전
• 방법
  • 하향식
    • 메모이제이션 (캐쉬 기법)
      • 누적 (이전 계산 재사용)
      • 재귀로 접근
  • 상향식
    • 타뷸레이션
      • 점화식 필요
      • 반복문으로 접근
• DAG에 적용 가능 (배열, 트리, 위상 정렬)
• 상향식 DP가 좋지 않은 경우
  • combination (파스칼 삼각형)
    • $C(n,m)=C(n-1,m)+C(n-1,m-1)$
      • 
    • 재귀는 목표한 값만 찾지만, 상향식 DP는 모든 파스칼 삼각형을 찾는다
      • 

피보나치

• 하향식
  • recursive
  • dp(n - 1) + dp(n - 2)
  • $O(2^n)$
  • 메모이제이션
    • dp_cache[n]에 구한 값 저장
    • $O(n)$
    • 스택사용으로 살짝 성능 저하
    • 캐쉬 사용으로 공간 복잡도 O(n)
• 상향식
  • $dp[1]=1$
  • $dp[2]=1$
  • $dp[N]=\min (dp[i-1]+dp[i-2])\text{for }i=0,1,\dots ,N)$
  • $O(N)$
• 선형수학
  • 행렬로 계산시 $O(log(n))$
• 다이내믹 프로그래밍 완전 정복 p.85

역 사이 최소 비용 구하기

• $minCost[N]=\min (minCost[i]+cost[i][N]\text{for }i=0,1,\dots ,N)$
• 상향식으로 최소 비용 갱신
• 다이내믹 프로그래밍 완전 정복 p.87

부분 문자열 다루기

• 숫자로 이루어진 문자열에서, 부분 문자열 중 앞의 절반과 뒤의 절반 숫자의 합이 같은 부분 문자열 중, 가장 긴 부분 문자열의 길이
• $k=(i+j)/2\text{mid value}$
• $S(i,j)=S(i,k)+S(k+1,j)$
• 다이내믹 프로그래밍 완전 정복 p.89

행렬에서 최소 이동 비용

• $m=row\mid n=column$
• $1\le i<m,1\le j<n$
• $\text{mem}(i,j)=\min (\text{mem}(i-1,j),\text{mem}(i,j-1))+\text{cost}(i,j)$
• 
• 다이내믹 프로그래밍 완전 정복 p.105

특정 점수에 도달하는 경우의 수 구하기

• 한번에 3, 5, 10점 얻을 수 있다
• 재귀의 경우
  • 
• 상향식
  • $\text{for }i=0,1,\dots ,N$
  • $i-3\ge 0\text{arr}[i]=\text{arr}[i]+\text{arr}[i-3]$
  • $i-5\ge 0\text{arr}[i]=\text{arr}[i]+\text{arr}[i-5]$
  • $i-10\ge 0\text{arr}[i]=\text{arr}[i]+\text{arr}[i-10]$
  • $target=\text{arr}[N]$
• 다이내믹 프로그래밍 완전 정복 p.121

연속된 부분 배열의 최댓값 구하기

• 카데인 알고리즘(Kadane’s algorithm)
  • $\text{M}(n)=\max (\text{M}(n-1)+\text{arr}[n],\text{arr}(n))$
• 다이내믹 프로그래밍 완전 정복 p.122

최소 교정 비용 문제

• 두 단어가 주어졌을 때, 두 단어가 똑같아 지는데 드는 교정 횟수
• 2차원 DP (각 두 단어의 차원)
  • $1\le i<m,1\le j<n$
  • 첫 행, 열을 시퀀스하게 초기화
    • 반대 글자가 비어있다면, 교정비용은 내 현재 글자 수만큼이다
  • 같으면
    • $dp[i][j]=dp[i-1][j-1]$
    • 좌상 대각선 값
  • 다르면
    • $dp[i][j]=\min (dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1$
    • 위쪽 셀, 왼쪽 셀, 왼쪽 위 셀의 값의 최솟 값 + 1
  • $target=dp[m][n]$
  • 
• 다이내믹 프로그래밍 완전 정복 p.130

직사각형에서 총 경로 수 구하기

• M x N개의 방으로 구성된 직사각형이 있을 때, 좌상단 방에서 우하단 방까지 이동하는 모든 경로의 수
• 이동 - 오른쪽, 아래 한칸 씩
• 재귀
  • 
  • 지수 시간 $2^n$
• 상향식
  • 2차원 DP
  • $dp[i][j]=dp[i-1][j]+dp[i][j-1]$
  • 
  • 다항 시간 $n^2$
• 다이내믹 프로그래밍 완전 정복 p.137

문자열 인터리빙 확인 문제

• 두 문자열 A, B의 모든 글자의 상대적인 순서가 유지 된채 섞여서 새로운 문자열 C가 만들어지면 이는 인터리빙이라 부른다
  • A = ‘xyz’
  • B = ‘abcd’
  • C = ‘xabyczd’ - 인터리빙
• 재귀
  • 
• 상향식
  • 2차원 DP (A, B)
  • A = ‘bbca’, B = ‘bcc’, C = ‘bbcbcac’
  • 각 셀의 경우 (C의 현재 글자가)
    • A의 글자와 같고, B와 다를때
      • 바로 위 셀값 (B가 다르니, B에 의존적)
    • B의 글자와 같고, A와 다를때
      • 바로 왼쪽 셀값 (A가 다르니, A에 의존적)
    • A, B 둘다와 같을 때
      • 왼쪽, 위쪽 셀값 중, True가 있으면 True
    • A, B 둘다와 다를 때
      • False
  • 
• 다이내믹 프로그래밍 완전 정복 p.144

부분집합의 합 구하기

• 0과 양의 정수로 이루어진 집합에서, 부분집합의 원소 합이 X인 것이 존재하는지
• c - {3, 2, 7, 1}, X = 6
  • {3, 2, 1}
• 재귀
  • 포함하는 경우 || 포함하지 않는 경우
  • $2^n$
• 상향식
  • 2차원 DP
    • 행 - 집합 원소
    • 열 - 타겟 넘버 까지의 시퀀스
  • 중간 결과를 배열에 저장
    • subsum[i][j] 는 부분집합의 첫 (i + 1)개의 원소로 구성된 합에 대해서 합이 j$(O\le j\le X)$인 부분집합이 있는지에 대한 boolean
  • subsum[i][0] 를 $v$ 로 정의
  • 초기 조건
    • 
    • 첫 행은 $v$와 j가 똑같으면 T
    • 첫 열은 공집합이기에 항상 T
  • 두 번째 행부터, $v$의 값만큼 위 셀에서 복사
    • $v$의 값이 셀에 영향이 없기에
    • 바로 위쪽 셀이 T면 T
    • $(i-1,j-v)$ 셀의 값을 $(i,j)$로 복사
    • 
  • $v$가 $X$보다 크다면 바로 위 행을 복사
    • 타겟 넘버보다 크기에
    • 아래 그림 $7$ 값인 3행은 위의 값을 그대로 복사
  • 
• boolean 대신 숫자로 한다면, 그 점수에 도달하는 가짓수 도출 가능
  • 단 한번만 사용은 위에 행에서 [i - 1][j - v] | [i - 1][j]
    • 한번만 사용이니, 이전 행에 영향을 받는다
  • 무제한 사용은 자기 행에서 [i][j - v] + [i - 1][j],
    • 번호 중복 사용, 순서 상관 없는 경우({1, 1, 2} == {2, 1, 1} 즉 같은 집합인 경우)
• 다이내믹 프로그래밍 완전 정복 p.152

최장 공통 부분 수열 길이 구하기 (LCS)

• 두 문자열 $X,Y$의 최장 공통 부분 수열
  • $X$의 부분 수열 이면서, $Y$의 부분 수열은 공통 부분 수열(Common subsequence)
• 재귀
  • 뒤 글자 부터
  • 같으면 뒤글자 제외
    • LCS_LENGTH('ABCD', 'AEBD') = 1 + LCS_LENGTH('ABC', 'AEB')
  • 다르면 각 $X,Y$에서 뒤글자 없는 경우의 최대
    • LCS_LENGTH('ABCD', 'AEBD') = MAX(LCS_LENGTH('ABCD', 'AEB'), LCS_LENGTH('ABC', 'AEBD'))
  • 메모이제이션
    • LCSLTable[m][n]
• 상향식
  • 상향식으로 캐시 테이블
  • 2차원 DP
    • 행 - $X$
    • 열 - $Y$
  • 초기 값
    • 
  • 글자가 같으면
    • 좌상 대각선 값 + 1
  • 다르면
    • MAX(위쪽 셀값, 왼쪽 셀값)
  • 
  • 최장 공통 부분 수열 출력
    • 대각선 이동시 LCS 추가된다
    • 완성된 DP 테이블에서 역순으로 순회
    • 같으면 포함
    • 다르면 왼쪽, 위쪽 셀 값중 큰 곳으로 이동
• 다이내믹 프로그래밍 완전 정복 p.158

거스름돈 최적화 (Coin Change)

• 그리디로 해결 안되는 경우

  Transclude of Greedy#^6d4b0e

• 재귀
  • coin[i] 는 사용 가능한 종류의 동전 액면가
  • $\text{for }i=0,1,\dots ,N$
  • $minCoins(S)=1+\min (minCoins(S-coin[0]),minCoins(S-coin[1]),\dots ,minCoins(S-coin[N-1]))$
• 상향식
  • 
    • 1원부터 ~ $S$원 까지
    • 각 동전 별로 다시 순회하며 최소값 갱신
  • dp[n][T]
    • dp[i][j] = dp[i - 1][j]
    • dp[i][j] += dp[i][j - coin[i]]
  • n is coin size
  • T is target number
  • 경우의 수를 구할땐 숫자로 기입, 존재 여부를 구할 땐 True, False
  • 기저
    • d[i][0] = 1 or True
  • 메모리 최대 $O(T)$ 으로도 가능
    • 직전 만 참조함으로, 벡터 2줄로 가능 next_dp
• 다이내믹 프로그래밍 완전 정복 p.171

철근 자르기

• 다이내믹 프로그래밍 완전 정복 p.176

0-1 배낭

• $n$개의 물건, 무게와 가격 고정
• $c$ 용량의 배낭에 물건을 넣었을때, 가능한 물건 가격의 최댓값
• 재귀
  • 물건 포함
    • value[n - 1]의 가치 추가
    • n - 1개의 물건 남음
    • c - weight[n - 1]의 남은 가용 용량
  • 물건 미포함
    • n - 1개의 물건 남음
    • $c$의 남은 가용 용량
• 상향식
  • 2 차원 DP
    • 행 - 물건을 나타내는 인덱스
    • 열 - 0부터 $c$ 까지 시퀀스한 무게
    • $(i,j)$는 $i$번 까지의 물건을 용량 $j$의 배낭에 집어 넣은 최대 가격
  • 물건 무게가 배낭의 용량보다 크면 위쪽 셀을 복사
    • maxValue[i - 1][j]
  • $i$번째 물건을 선택하지 않았을 때 최대가격
    • maxValue[i - 1][j]
    • i - 1 인 이유
      • 이전 행의 물건 가격 계승
  • $i$번째 물건을 선택했을 때 최대가격
    • value[i - 1] + maxValue[i - 1][j - weight[i - 1]]
    • $j$ 선택한 물건의 무게를 뺀 위치 즉, 남은 용량

    •   dp[i][w] = max(
        	dp[i-1][w],                         // i번째 물건을 선택하지 않음
        	dp[i-1][w - weight[i]] + value[i]   // i번째 물건을 선택함
        )

  • 
• 다이내믹 프로그래밍 완전 정복 p.182

계단 오르기 - 2579

• 2개의 1차원 dp 배열 ($A,B$)
• 연속 계단 3개 불가능
• $A=\text{직전 계단 사용 X}$
• $B=\text{직전 계단 사용 O}$
• $A_n=S[n]+\max (A_{n-2},B_{n-2})$
• $B_n=S[n]+S[n-1]+MAX(A_{n-3},B_{n-3})$

LIS (최장 증가 부분 수열 길이 구하기)

•  int n;
   cin >> n;
   vector<int> a(n), dp(n, 1);
   for (int i = 0; i < n; i++) cin >> a[i];
   
   for (int i = 1; i < n; i++) {
       for (int j = 0; j < i; j++) {
           if (a[j] < a[i]) {
               dp[i] = max(dp[i], dp[j] + 1);
           }
       }
   }
   
   cout << *max_element(dp.begin(), dp.end());

• dp[i]는 a[i]를 마지막 원소로 갖는 LIS의 길이
• 현재 글자의, 이전 글자들 대소 비교로, dp 업데이트
  • 이미 왼쪽부터 dp가 정복하니 최적해 보장
• $O(N^2)$