發表新討論
#24379: DP


hshua (hshua)

學校 : 新北市立林口高級中學
編號 : 52506
來源 : [125.228.147.181]
最後登入時間 ：
2024-05-02 20:52:39
d652. 貪婪之糊 -- jack1 | From: [61.223.85.146] | 發表日期 : 2021-02-10 17:21

動態規劃 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]

 
ZeroJudge Forum