發表新討論
#39091: DP--Matrix Chain Multiplication的變形


nonamegogo (nonamegogo)

學校 : 臺北市立中山女子高級中學
編號 : 19794
來源 : [223.140.240.39]
最後登入時間 ：
2024-09-04 21:41:44
m934. 4. 合併成本 -- 2024年1月APCS | From: [223.140.174.221] | 發表日期 : 2024-01-12 23:02 
DP--Matrix Chain Multiplication的變形

c[i][j]紀錄合併a[i]到a[j]的最低花費
v[i][j]紀錄合併a[i]到a[j]後的數值

根據花費與數值的定義
i<=k<=j
c[i][j] = min(c[i][j], c[i][k] + c[k + 1][j] + abs(v[i][k]-v[k+1][j]));
v[i][j] = v[i][k] + v[k + 1][j];  //更新節點的值

https://sites.google.com/view/zsgititit/home/apcs/apcs202401%E7%AC%AC4%E9%A1%8C-%E5%90%88%E4%BD%B5%E6%88%90%E6%9C%AC
 
#39425: Re: DP--Matrix Chain Multiplication的變形


wubaie (小億)

學校 : 不指定學校
編號 : 123253
來源 : [111.240.1.39]
最後登入時間 ：
2024-11-07 18:39:23
m934. 4. 合併成本 -- 2024年1月APCS | From: [220.133.154.226] | 發表日期 : 2024-02-18 22:50 
DP--Matrix Chain Multiplication的變形

c[i][j]紀錄合併a[i]到a[j]的最低花費
v[i][j]紀錄合併a[i]到a[j]後的數值

根據花費與數值的定義
i<=k<=j
c[i][j] = min(c[i][j], c[i][k] + c[k + 1][j] + abs(v[i][k]-v[k+1][j]));
v[i][j] = v[i][k] + v[k + 1][j];  //更新節點的值

https://sites.google.com/view/zsgititit/home/apcs/apcs202401%E7%AC%AC4%E9%A1%8C-%E5%90%88%E4%BD%B5%E6%88%90%E6%9C%AC
應該是 i<=k<j ，不然 k+1 會大於 j



 
ZeroJudge Forum