>[danger]小紅拿到長度為n的數組，陡峭值是相鄰兩數差的絕對值之和，求只修改第i個元素，讓f（i）最小的各個陡峭值 這個問題可以使用動態規劃來解決。我們可以先計算出原數組的陡峭值，然后枚舉每個元素，對于每個元素，假設我們將其修改為 x，那么它對答案的貢獻就是：原本在 i-1 和 i 之間的兩個數變成了 i-1 和 x 之間的數，以及 i 和 i+1 之間的兩個數變成了 x 和 i+1 之間的數，所以它對答案的貢獻就是： ``` abs(x - a[i-1]) + abs(x - a[i+1]) - abs(a[i] - a[i-1]) - abs(a[i] - a[i+1]) ``` 其中 a 是原數組，|x-y| 表示 x 和 y 之間的絕對距離。我們需要找到一個 x，使得上述表達式最小。 為了方便計算，我們可以先把原數組中相鄰兩個數之間的差的絕對值都計算出來，存入一個數組 b 中。也就是說，b[i] = |a[i]-a[i+1]|。 然后我們可以用一個數組 dp 來記錄每個位置 i 修改后能夠獲得的最小的陡峭值。顯然 dp[1] 一定是 0，因為第一個數無論如何都不會影響第一個陡峭值。接下來，我們從 2 開始枚舉每個位置 i，對于每個位置 i，我們嘗試將它修改為 0 到 n-1 中的每個數，計算上面的表達式，取最小值作為 dp[i] 的值。 轉移方程如下： ``` dp[i] = min(dp[j] + abs(a[i]-a[j]) - b[j] + b[i-1] - abs(a[i-1]-a[j])) (j從1到n-1) ``` 其中 dp[j] 表示修改第 j 個元素后得到的最小陡峭值，abs(a[i]-a[j]) 表示修改 a[i] 后第 i 個差的絕對值變成了 abs(a[i]-a[j])，-b[j] 表示將第 j 個差的絕對值從原來的 b[j] 改成了 abs(a[i]-a[j])，b[i-1] 表示將原來在 i-1 和 i 之間的差的絕對值 b[i-1] 從原來的答案中撤銷，abs(a[i-1]-a[j]) 表示把它改為 abs(a[i-1]-a[j])，因為現在第 i 位已經變成了 a[j]。 最終答案即為 min(dp[1]...dp[n-1])。 代碼如下： ```javascript function solve(a) { const n = a.length; const b = new Array(n - 1); // 存儲相鄰兩數之差的絕對值 for (let i = 0; i < n - 1; i++) { b[i] = Math.abs(a[i] - a[i + 1]); } const dp = new Array(n).fill(Infinity); dp[1] = 0; for (let i = 2; i < n; i++) { for (let j = 1; j < n - 1; j++) { dp[i] = Math.min(dp[i], dp[j] + Math.abs(a[i] - a[j]) - b[j] + b[i - 1] - Math.abs(a[i - 1] - a[j])); } } return Math.min(...dp.slice(1)); } ```