💡 DP(Dynamic Programming)

• Dynamic Programming = 동적 계획법
• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
• 부분 문제 반복과 최적 부분 구조를 가진 알고리즘을 더욱 적은 시간 내에 풀 때 사용

💻 원리

• 일반적으로 주어진 문제를 풀기 위해, 문제를 여러 개의 하위 문제로 나누어 푼다
• 나누어 푼 것을 결합하여 최종적인 목적에 도달하는 것
• 각 하위 문제를 해결한 뒤 해결책을 저장하여, 후에 하위 문제가 나왔을 경우 저장해둔 것을 사용해 간단하게 해결

  따라서 동적 계획법은 계산 횟수를 줄일 수 있다. 하위 문제의 수가 기하급수적으로 증가할 때 유용함

• 가능한 모든 방법을 고려해야 한다는 단점이 있음
  (이를 극복하기 위해 나온 것이 그리디 알고리즘)

📝 문제 링크

https://www.acmicpc.net/problem/11726

👩‍💻 적용

1. Top-Down : 재귀 함수

let memo = new Array(1001).fill(-1)
memo[1] = 1
memo[2] = 2

function dp(cur) {
  if (cur == 1) {
    return memo[1]
  }
  if (cur == 2) {
    return memo[2]
  }

  if (memo[cur] !== -1) {
    return memo[cur]
  }
  memo[cur] = (dp(cur - 1) + dp(cur - 2)) % 10007

  return memo[cur]
}

dp(1000);

console.log(memo[count])

2. Bottom-Up : 반복문

let dp = new Array(1001);

dp[0] = 1;
dp[1] = 2;

for (let i = 2; i < dp.length; ++i) {
  dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
}

console.log(dp[count - 1]);

• 상태 정의 : dp 배열을 만들었을 때 index 값이 의미하는 상태
• ex) dp[0] = 2x1 크기의 직사각형을 타일로 채우는 경우의 수 / dp[1] = 2x2 크기의 직사각형을 타일로 채우는 경우의 수
  즉, dp[i] = 2x(i+1) 크기의 직사각형을 타일로 채우는 경우의 수
• 점화식 구하기 : dp[i] = dp[i-1]+dp[i-2]