다이나믹 프로그래밍(DP)

참고사이트: 패스트캠퍼스 코딩+알고리즘 완주반 6강 실전 문제풀이

방법

다음 상태를 저장하고, 사용하기 -> 메모이제이션을 이용해 푸는 것

🤷🏻‍♀️ 어려운 이유

무엇을 저장해야할지 모르고, 어떻게 저장해야할지 모르고, 방법 자체가 수학 문제를 많이 풀어보지 않으면 당혹스럽다.

Ex. 피보나치수열 등등
코테에서는 난이도 상의 문제보다는 하, 중 문제들이 변형 되어 나온다.
Ex. 피보나치 수열이 두 수가 아니라 세개의 수가 된다든지

✏️ 푸는 순서

1. 상태를 정의한다.
2. 점화식을 찾는다 (구한다)
3. 시간복잡도를 계산한다.
4. 코딩한다.

• 상태를 정의한다.
  : 2차원 배열을 만든다고 가정할 때 i, j가 무엇을 의미하는지, 초기상태가 무엇인지를 명확히 하는 것 .

✏️ 푸는 방법

1. Top-Down (재귀)
2. Bottom-Up (반복문)

C나 Java같은 경우는 1,2번 상관 없는 데, 파이썬의 경우 1번으로 풀면 살짝 아슬아슬할 수 있다.
그래서 2번 추천