이것도 전형적인 DP문제다.
dp[i][j]를 i번째부터 j번째까지의 행렬을 곱했을 때의 최소 연산 횟수로 저장한다.
그리고 i번째부터 j번째까지의 행렬의 곱은 i번째랑 나머지, (i번째, i+1번째)와 나머지, ... , (나머지)와 j번째 행렬의 곱으로 나누어서 생각할 수 있다. 그럼 그 중 최소가 되는 것을 골라 업데이트해준다.
'백준 > DP' 카테고리의 다른 글
| 백준 1720번 타일 코드 (0) | 2022.03.08 |
|---|---|
| 백준 17404번 RGB거리 2 (0) | 2022.03.06 |
| 백준 2342번 Dance Dance Revolution (0) | 2022.03.06 |
| 백준 1695번 (0) | 2022.02.17 |
| 백준 1563번 (0) | 2022.02.17 |