Изменения
→Наивное решение
dp[1] = 0
dp[2] = dp[3] = ... = dp[n] = <tex>\infty</tex>
'''for''' i = 1..n-1 {
dp[i] = +<tex>\infty</tex>
'''for''' j = 0..i-1 {
'''if''' (dp[j] + a[i] <tex>\cdot</tex> c[j] < dp[i])
dp[i] = dp[j] + a[i] <tex>\cdot</tex> c[j]
'''return''' dp[n]
Нетрудно видеть, что такая динамика работает за <tex>O(n^2)</tex>.
