https://leetcode.com/problems/arithmetic-slices-ii-subsequence/
- 일단 풀이가 3가지가 있었는데, 가장 쉬운 종류의 풀이도 생각하질 못했다.
-
핵심 아이디어 중 하나는 “dp 식의 결과물이 꼭 정답일 필요가 없다.” 이다.
- 이번 문제에서 dp 식이 아래와 같았는데, 정답은 $dp[A_i][A_N-A_i]$ 부분만 누적하는 것이 포인트이다. 즉 현재 dp는 다음 계산을 위한 저장이고, 이 저장된 것이 사용된 후에야, 답에 포함되는 것이다.
- 이런 구조가 나오는 이유는 최소한 3개째가 되어야 답으로 인정해 주기 때문이다. 기존의 익숙한 방법으로 풀면, 최소 앞선 2개를 검사해야 한다.
- 즉 $A_N=3$인 상황에서 $A_i=2$라면 , $A_i=1$ 인 곳까지 확인한 뒤에야 정답을 1 증가시킬 수 있다. 즉 $O(N^3)$으로 귀결된다.
- 만약 $A_i=2$과 $A_i=1$를 나란히 보았을 때, 이미 1을 증가해두었다면 이를 $A_N=3$이 발견될 때 답으로 포함시키고, $dp[N][1] = 2$로 표시해 둘 수 있다.
- 이러한 구조에서 속도 증가 풀이들이 나오는데, 주로 미래에 사용되지 않을 값들을 아예 계산하지 않는식으로 가지를 쳐버린다. solution의 2가지 풀이를 보고 다시 풀어볼 것.