Dynamic Programming (동적 프로그래밍)

1. 단순한 점화식을 사용하여 해결

// example
dp[i] = dp[i - 1] + dp[i - 2]; 
dp[i] = dp[i - 1] + n * dp[i - 2];

2×n 타일링 2

1, 2, 3 더하기

1, 2, 3 더하기 3

2. dp[i] 와 dp[i - ?] 를 비교하여 그중 max값 혹은 min값 넣기

// example
dp[i] = Math.max(dp[i], dp[i - j]); 
dp[i] = Math.min(dp[i], dp[i - j]);

카드 구매하기

카드 구매하기 2

가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열 4

제곱수의 합

가장 큰 증가 부분 수열

가장 긴 감소하는 부분 수열

3. 2차원 배열 사용하기 (dp[i][j])

// example
if (j === 0) {
  dp[i][j] = dp[i - 1][0] + dp[i - 2][1];
}

1, 2, 3 더하기 5

쉬운 계단 수