[일반] memoization 보니까 생각난거

[익명(1.225)]

사람들 매번 백트래킹 짠 다음에 memoization으로 푼다고 저장하는 배열 추가하는 식으로 풀던데

이런거 볼 때마다 가슴이 아프다.

[시아닌(kimjg1119)]

그럼 대체 어떻게 풀건데? 반복문 돌리면서 테이블 채우는 순서 고민하느라 머리쓰는것보다 그냥 타이핑 몇줄 더 하는게 나을수도 있음

[하루룽(ailedear)]

ㄴ이게맞는거갓은대

[시아닌(kimjg1119)]

그리고 모든 저장공간을 쓰지 않는 O(lgn) DP는 메모이제이션으로만 해결할 수 있는 경우도 있음. 아만보