#24379: __DP


hshua (hshua)


動態規劃 dp,

令dp[i][j]代表區間(i,j)的最小值,則:

dp[i][j] = min( dp[i][j] ,  dp[i][k] + dp[k][j] + v[i] * v[k] * v[j] )  

範圍長度L=j-i,窮舉k值

(初值 dp[][] 先計算 L=3 的情況, L=1, L=2 皆為0)

 

v[i] ----- v[k] ------ v[j]