90
правок
Изменения
м
→Динамическое программирование
//l — включая в отрезок
//r — исключая из отрезка
if dp[l][r] == -1 //Если значение динамики не посчитано
if l == r - 1
dp[l][r] = 0;//Если у нас подотрезок длины 1, то количество операций для перемножения равно нулю
else
dp[l][r] = 1000 * 1000 * 1000INFINITY;
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));
