Изменения

Перейти к: навигация, поиск

Задача о порядке перемножения матриц

201 байт убрано, 04:28, 12 декабря 2011
Псевдокод
int dp[1000][1000];
vector<pair<int, int> > v;// v[i].first — размер i-той матрицы по горизонтали // v[i].second — размер i-той матрицы по вертикали;
// dp[i][j] — меморизация на отрезке [i, j)
int matrixChainMultiplication(int l, int r)
dp[l][r] = 0; //Если у нас подотрезок длины 1, то количество операций для перемножения равно нулю
else
dp[l][r] = INFINITYinfinity;
for (int i = l + 1; i < r; i++)
dp[l][r] = min(dp[l][r], v[l].first * v[i].first * v[r - 1].second + matrixChainMultiplication(l, i) + matrixChainMultiplication(i, r));
return dp[l][r];
}
90
правок

Навигация