Matrix Chain Multiplication
advanced
Bir matris zincirinin çarpımı için minimum skaler çarpma sayısını bul. Matrisler soldan sağa çarpılır.
Örnek: p = [1, 2, 3, 4] (3 matris: 1x2, 2x3, 3x4) → 18.
İpuçları
- 💡 İpucu 1: dp[i][j] = matris i..j çarpımı için min cost.
- 💡 İpucu 2: Tüm k parçaları için böl: dp[i][j] = min(dp[i][k] + dp[k][j] + dims[i]*dims[k]*dims[j]).
- 💡 İpucu 3: O(n³) DP, Knuth optimization ile O(n²) iyileştirme mümkün.
Örnek Test Case'ler
💡 Kodu çalıştırmak ve gerçek çıktılarını görmek için üye girişi yapıp editöre geçebilirsin.