Изменения
→Наивное решение
Посмотрим на код выше описанного решения:
'''int''' simple-dp('''int''' a[], '''int''' c[], '''int''' n) 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 {
dp[i] = dp[j] + a[i] * c[j]
}
} '''return''' dp[n]
Нетрудно видеть, что такая динамика работает за <tex>O(n^2)</tex>.
