저도 같은 접근방식으로 풀었다가 틀린부분을 알게되었습니다.
5년이나 지났지만 혹시 다른분들이 볼수도 있으니 댓글 남깁니다.
1차원으로 접근해서
1. 이전 결과(dp[i-1]) 에 바로 현재 행렬을 붙이는 방식
2. 이전 이전 결과 (dp[i-2])에 이전 행렬 과 현재 행렬의 곱을 붙이는 방식
은 모든 곱셈 순서를 커버하지 못합니다.
예를 들어 위 방식은 ABCD 네개의 행렬을 BC -> BCD -> ABCD 순서가 최소가 되는 경우를 커버 할 수 없습니다.
추가로 관련 반례입니다.
```
4
3 2
2 100
100 2
2 1
406
```
WA : 418 (제 코드도 418 나오네요.. 고치러 가야겠습니다)
his130 6년 전
D[N] = N번째 행렬의 곱까지 최솟값 이라고 점화식을 세워서 풀어봤습니다.
그리고 마지막 N번째 수가 묶이지 않았을 때와, N번째수와 N-1번째 수가 묶였을 때로 나누었습니다.
예를 들면 ABCDE (마지막 E를 제외한 앞의 수가 묶여있음) 과 ABC(DE) 이런식입니다.
(제 생각에 이는 모든 케이스에 들어간다고 생각합니다.)
그래서
N번째 수가 묶이지 않았을 때는
D[N]= D[N-1] + v[0].first * v[N-1].first * v[N-1].second ;
N-1번째까지 값에 마지막 N번째 행렬의곱까지 구하면 된다고 생각했고,
N번째 수가 N-1번째랑 묶였을 경우에는,
D[N] = D[N-2] + v[N-2].first * v[N-1].first * v[N-1].second + v[0].first * v[N-2].first * v[N-1].second ;
즉, N-2 번째까지 곱에 N-2 ,N-1 행렬의 곱의 합과 , 그 결과를 다시 앞의 행렬과 곱한 결과를 더하면 된다고 생각했습니다.
그래서 위의 두 값 중에 최솟값을 선택하는 방식으로 구현하였습니다.
그랬더니 시간초과가 발생했습니다.
그래서 초기값 문제인가 싶어 아래코드로 바꾸면 틀렸습니다가 나옵니다.
이런식으로 코드를 구현하면 어떤 곳에서 오류가 생기는 걸까요? 제 생각에는 모든 케이스를 검토할 것 같은데..
DP 공부중에 1차식으로 해야할지, 2차식으로 해야할지 감이 안 잡히네요 아직..