순서대로 알려드리면,
0. 어떤 문제의 답 a가 어떤 sequence S의 n번째 항이라는 것을 캐치합니다.
1. 먼저 S의 recurrence relation R을 적습니다.
EX.
F(1)=F(2)=1(initial condition) and
F(i)=F(i-1)+F(i-2) for 3<=i
2. R을 이용해 S[0], S[1], ... S[n] = a 를 계산합니다.
Ex. 그런데 이 때, 위의 F를 예로 보면, 필요한 메모리가 O(n)이 아닌 O(1)임을 알 수 있습니다. 메모리를 재활용하면 되기 때문입니다.
seanrocket17 7년 전
사이트 여기저기를 뒤져보니까 dp[3]으로 해서 그때그때만 저장하는 식으로 하면 된다고 했는데 어떻게 해야하죠?????
아래 코드는 메모리 초과가 나는 코드입니다...........한마디로 dp[3]으로 어떻게 풀죠????