We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
using namespace std;
int minCostMatrixMultiplication(vector& dimensions) {
int n = dimensions.size() - 1;
vector> dp(n, vector(n, 0));
for (int len = 1; len < n; len++) {
for (int i = 0; i < n - len; i++) {
int j = i + len;
dp[i][j] = INT_MAX;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
dp[i][j] = min(dp[i][j], cost);
}
}
}
return dp[0][n - 1];
}
int main() {
int n;
cin >> n;
vector dimensions(n + 1);
for (int i = 0; i <= n; i++) {
cin >> dimensions[i];
}
int result = minCostMatrixMultiplication(dimensions);
cout<
return 0;
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Linear Algebra Foundations #4- Matrix Multiplication
You are viewing a single comment's thread. Return to all comments →
include
include
include
using namespace std; int minCostMatrixMultiplication(vector& dimensions) { int n = dimensions.size() - 1; vector> dp(n, vector(n, 0)); for (int len = 1; len < n; len++) { for (int i = 0; i < n - len; i++) { int j = i + len; dp[i][j] = INT_MAX; for (int k = i; k < j; k++) { int cost = dp[i][k] + dp[k + 1][j] + dimensions[i] * dimensions[k + 1] * dimensions[j + 1]; dp[i][j] = min(dp[i][j], cost); } } } return dp[0][n - 1]; } int main() { int n; cin >> n; vector dimensions(n + 1); for (int i = 0; i <= n; i++) { cin >> dimensions[i]; } int result = minCostMatrixMultiplication(dimensions); cout<
}