Изменения

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

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] = ~~INFINITY~~infinity;

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

правок