APCS202401第4題 合併成本

出處：APCS20240107

題目：https://zerojudge.tw/ShowProblem?problemid=m934

解題策略：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];  //更新節點的值