old_Dynamic_Programming/Matrix_Chain_Multiplication.cpp

• View this file on GitHub
• Last update: 2022-07-19 22:14:43+09:00

Code

long long matrix_chain_multiplication(vector<long long> &A){
	int n = A.size() - 1;
	vector<vector<long long>> dp(n, vector<long long>(n, INF));
	for (int i = 0; i < n; i++){
		dp[i][i] = 0;
	}
	for (int i = 1; i < n; i++){
		for (int j = 0; j < n - i; j++){
			for (int k = j; k < j + i; k++){
				dp[j][j + i] = min(dp[j][j + i], dp[j][k] + dp[k + 1][j + i] + A[j] * A[k + 1] * A[j + i + 1]);
			}
		}
	}
	return dp[0][n - 1];
}

#line 1 "old_Dynamic_Programming/Matrix_Chain_Multiplication.cpp"
long long matrix_chain_multiplication(vector<long long> &A){
	int n = A.size() - 1;
	vector<vector<long long>> dp(n, vector<long long>(n, INF));
	for (int i = 0; i < n; i++){
		dp[i][i] = 0;
	}
	for (int i = 1; i < n; i++){
		for (int j = 0; j < n - i; j++){
			for (int k = j; k < j + i; k++){
				dp[j][j + i] = min(dp[j][j + i], dp[j][k] + dp[k + 1][j + i] + A[j] * A[k + 1] * A[j + i + 1]);
			}
		}
	}
	return dp[0][n - 1];
}

Back to top page