07. dynamic programming.md

Dynamic Programming;동적계획법

• 복잡한 문제를 간단한 부분 문제로 재귀적으로 분해하여 단순화, 직관화
• 부분 문제의 답을 기록, 데이터 범위를 확장. 넓힌 범위의 답은 이전에 구한 답을 이용
• 부분 문제에서 계산한 값은 dynamic table 에 저장(memoization)
• 관계식(점화식)을 잡아내는 것이 핵심

적용 조건

• 겹치는 부분 문제 (Overlapping Subproblem):
  같은 부분 문제가 여러 번 재사용되거나, 재귀를 통해 해결되어야 한다.
• 최적 부분 구조 (Optimal Substructure):
  문제의 최적 해결책은 부분 문제의 최적 해결책으로부터 설계될 수 있어야 한다.

// section10 1번 문제
const solution = (n) => {
  let answer = 0;
  // dynamic 배열: 다이나믹 테이블. n 번째에 정답이 기록됨
  const dy = Array.from({ length: n + 1 }, () => 0);

  dy[1] = 1;
  dy[2] = 2;
  // 현재 위치의 계단에 오르기 위한 경우의 수는
  // 직전 2개 계단의 값을 더한 값이다.
  for (let i = 3; i <= n; i++) {
    dy[i] = dy[i - 2] + dy[i - 1];
  }
  answer = dy[n];
  return answer;
};

console.log(solution(7));

/*
1번 계단은 1: 1가지, 2번 계단은 1+1, 2: 2가지
3번 계단은? 3가지:
1번 계단에서 오거나(1+2: 1가지),
2번 계단에서 오거나(1+1+1, 2+1: 2가지)
4번 계단은? 5가지:
2번 계단에서 오거나(1+1+2, 2+2: 2가지),
3번 계단에서 오거나(1+2+1, 1+1+1+1, 2+1+1: 3가지)
 */

동적계획법-냅색 알고리즘

• 조건에 대한 요소의 조합 최적화 알고리즘
• 각 항목들의 가중치와 가치, 그리고 가중치 제한이 주어질 때
  가중치 제한 내에서 항목들의 총 가치를 최대화하는 방법 탐색