251
правка
Изменения
→Псевдокод
<code>
'''int''' dp[][]; '''int''' v[];
<font color="green">// dp[i][j] — ответ на отрезке [i, j)
// Массив v[] — хранит все размеры матриц по порядку
// Так как у нас размеры соседних матриц по вертикали и горизонтали совпадают, то они занесены в этот массив однократно</font>
'''int''' matrixChainMultiplication(int l, int r)
<font color="green">//l — включая в отрезок
//r — исключая из отрезка</font>
'''if''' dp[l][r] == -1 <font color="green">//Если значение динамики не посчитано</font>
'''if''' l == r - 1
dp[l][r] = 0; <font color="green"> //Если у нас подотрезок длины 1, то количество операций для перемножения равно нулю</font>
'''else'''
dp[l][r] = infinity; '''for''' (int i = l + 1; i < '''to''' r; i++)- 1 dp[l][r] = min(dp[l][r], v[l] * v[i] * v[r - 1] + matrixChainMultiplication(l, i) + matrixChainMultiplication(i, r)); return dp[l][r]; }
</code>
