57 lines
1.4 KiB
C++
57 lines
1.4 KiB
C++
// Matrix Chain Multiplicatin - Memorization-Approuch
|
|
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
// Function for matrix chain multiplication
|
|
int matrixChainMulti(vector<int> &arr, const int i, const int j, vector<vector<int>> &dp)
|
|
{
|
|
if (i >= j)
|
|
return 0;
|
|
|
|
if (dp[i][j] != -1)
|
|
return dp[i][j];
|
|
|
|
int countMin = INT_MAX;
|
|
for (int k = i; k < j; k++)
|
|
{
|
|
int temp_ans = matrixChainMulti(arr, i, k, dp) + matrixChainMulti(arr, k + 1, j, dp) + (arr[i - 1] * arr[k] * arr[j]);
|
|
if (temp_ans < countMin)
|
|
countMin = temp_ans;
|
|
}
|
|
return dp[i][j] = countMin;
|
|
}
|
|
|
|
// Driver Code
|
|
int main()
|
|
{
|
|
// dp table initialized with -1
|
|
vector<vector<int>> dp(1001, vector<int>(1001, -1));
|
|
|
|
int n;
|
|
cout << "Enter the array size." << endl;
|
|
cin >> n;
|
|
vector<int> arr(n);
|
|
cout << "Enter all the array elements." << endl;
|
|
for (int i = 0; i < n; i++)
|
|
cin >> arr[i];
|
|
|
|
cout << "Minimum number of multiplications is" << endl;
|
|
cout << matrixChainMulti(arr, 1, n - 1, dp) << endl;
|
|
}
|
|
|
|
/*
|
|
* Time Complexity: O(N^3)
|
|
* Auxiliary Space: O(N^2)
|
|
|
|
* Input:
|
|
* n = 4
|
|
* arr = {10, 30, 5, 60}
|
|
* Output: 4500
|
|
* Explanation: The matrices have dimensions
|
|
* 10*30, 30*5, 5*60. Say the matrices are A, B
|
|
* and C. Out of all possible combinations,the
|
|
* most efficient way is (A*B)*C. The
|
|
* number of multiplications are: 10*30*5 + 10*5*60 = 4500.
|
|
*/
|