DP

• 분할정복

• 범위를 나눠서 계산할 수 있으며, 그 소범위의 최적해로 현재범위의 최적해를 구할 수 있다.

• DP

• 소범위들간에 겹치는 부분이 존재한다. -> 메모이제이션

• 최소최대, 경우의수를 구하는 문제인 경우 거의 다이나믹으로 해결가능

• 테스트케이스가 반절이상 맞았으나 시간초과 되는 경우 DP를 안해서일 가능성이 있다.

• 해결전략

• 기저케이스를 반드시 고려(리턴하는 조건을 함수 처음에)

• 문제에서 주어진 조건을 전부 배열 요소로 처리하여 DP배열을 생성

  • 이후 더 간략화 할 수 있으면 좋음(2개 조건이라 2차원 배열을 만들어야 하지만 해석방식에 따라 1개로도 줄일 수 있다)

• Bottom-up 일 경우 DP 의 초기배열값(0 또는 1)을 반드시 저장

• 하나의 루프(처리 프로세스)에서 해당 DP 값을 전부 채워야 함

  • DP[i][2][2] 크기라면 (0,0), (0,1), (1,0), (1,1) 을 매 프로세스마다 전부 채워야 한다.