LeetCode 70 Climbing Stairs 풀이: 1차원 동적 계획법
LeetCode 70 Climbing Stairs에서 마지막 이동이 한 칸인지 두 칸인지 나눠 점화식을 세운다. 피보나치 형태의 상태 전이를 이용해 O(1) 공간으로 계단 오르는 방법의 수를 구한다.
#동적계획법
작은 문제의 결과를 재사용해 전체 문제를 해결하는 동적 계획법 문제를 다룬다. 현재 6개의 풀이가 있다.
LeetCode 322 Coin Change 풀이: 최소 동전 수를 구하는 동적 계획법
LeetCode 322 Coin Change를 금액별 최소 동전 수를 저장하는 상향식 동적 계획법으로 푼다. 그리디가 실패하는 이유와 만들 수 없는 금액의 처리를 설명한다.
LeetCode 198 House Robber 풀이: 두 상태를 유지하는 동적 계획법
LeetCode 198 House Robber에서 이웃한 집을 함께 선택할 수 없다는 조건으로 최대 금액을 계산한다. 직전 두 상태만 유지하는 동적 계획법으로 공간을 O(1)로 줄인다.
LeetCode 62 Unique Paths 풀이: 격자 경로 동적 계획법
LeetCode 62 Unique Paths에서 각 칸에 도착하는 경로 수를 누적하는 동적 계획법을 적용한다. 한 행의 값만 유지해 O(n) 공간으로 최적화한다.
LeetCode 139 Word Break 풀이: 문자열 분할을 확인하는 동적 계획법
LeetCode 139 Word Break에서 각 접두사를 사전 단어로 만들 수 있는지 동적 계획법으로 판정한다. 상태 정의와 set 조회, 문자열 슬라이싱 비용을 살펴본다.
프로그래머스 도둑질 풀이: 원형 집을 두 구간으로 나누는 동적 계획법
원형 배치 때문에 양 끝집을 동시에 고를 수 없는 조건을 두 선형 DP로 나눈다. 반열린 구간과 이전 두 상태만 사용해 백만 채 입력도 추가 배열 없이 처리한다.