給定一個包含 N 個元素的陣列，我需要將其拆分為 k 個子陣列，其中 k 可以介于 2 <= k <= N 之間。子陣列的分數由以下因素決定：
(左邊界點 - 子陣列的右邊界點)^2 max(子陣列)。
如果有意義的話，左邊界點將是元素的索引，右邊界點將是（元素的索引 1）。您可以將它們視為拆分陣列的點。
在 O(n^2) 中找到一個演算法，計算所有子陣列的分數之和，使其成為可能獲得的最低分數。
例如：
陣列 = [5,3,4,9,2,8]
子陣列 = [5,3], [4,9,2], [8]
第一個子陣列的分數 = (2-0)^2 (5) = 9
第二個子陣列的分數 = (5-2)^2 (9) = 18
第三個子陣列的分數 = (6-5)^2 (8) = 9
所有子陣列的所有分數之和 = 36。
我試圖做的事情：
我試圖選擇陣列的磁區，這樣：（左邊界點 - 子陣列的右邊界點）^2 < max（子陣列）但也避免 k = N 因為他們不會給我最低分數（我通過觀察反復試驗）。
但我不確定這是否是正確的方法。謝謝！
uj5u.com熱心網友回復：
動態編程可以在O(N^2). 由于這可能是家庭作業，我不會給你代碼。
我將從一個更簡單的問題開始，即如何解決這個問題1 <= k <= N。
與往常一樣，動態規劃可以自頂向下或自底向上進行。通常遞回比 memoize 更容易，這是自上而下的。但是在這種情況下，您的得分功能使自下而上變得更容易。
我們想要做的是結束一個陣列，通過起始長度，最好的解決方案。起始陣列是[5,3,4,9,2,8]。我們開始：
best = []
接下來我們想要最小值：
score of [5] = (5-5)**2 5 = 5
所以我們得到：
best = [5]
接下來我們要附加以下的最小值：
best[0] score of [3] = 5 (3-3)**2 3 = 8
score of [5, 3] = (5-3)**2 5 = 9
所以我們得到：
best = [5, 8]
接下來我們要附加以下的最小值：
best[1] score of [4] = 8 (4-4)**2 4 = 12
best[0] score of [3, 4] = 5 (3-4)**2 4 = 10
score of [5, 3, 4] = (4-5)**2 5 = 6
所以我們得到：
best = [5, 8, 6]
依此類推，直到我們得到：
best = [5, 8, 6, 15, 15, 16]
但有一個問題。16 代表以下的最小值：
best[4] score of [8]
best[3] score of [2, 8]
best[2] score of [9, 2, 8]
best[1] score of [4, 9, 2, 8]
best[0] score of [3, 4, 9, 2, 8]
score of [5, 3, 4, 9, 2, 8]
最后一個條目是k=1. 因此，您必須正確重新計算最后一分鐘才能確定答案。（在這種情況下，這是答案，因為 16 對應于 split [5, 3, 4], [9, 2, 8]，但您必須檢查。）
如果您以最簡單的方式實作這一點，您將獲得一個O(n^3)演算法，因為這些score of ...操作需要計算子串列、查看其端點并找到最大值。有O(n^2)這樣的計算，找到子串列和找到最大值是潛在的O(n)。但是，如果您對保持最大值的運行總數而不是每次都實際生成這些子串列有點聰明，那么您可以開始使用O(n^2).
uj5u.com熱心網友回復：
我將采用偽代碼的方法：
- 使用一個簡單的候選解決方案開始呼叫遞回函式：一個包含 N 個子陣列的串列，其值為 V。
- 您可以先將其拆分為值 v < V 的任何較小子陣列。其余部分必須拆分為總值 < V - v。
分裂被 v < V 修剪（候選丟棄）。這可以通過一些額外的數學來改進。1 個元素 x 的子陣列具有值 x。所以 v x < V 對于一個較小的子陣列。
復雜度確實是 O(N^2)，因為下一個較大子陣列的值計算是基于先驗最大值、先驗邊界和新元素。
我不會為你破壞實際的編碼。
值計算需要一些思考（先驗最大值、邊界）和拆分。后者我會從 a 開始，List<int[]>但它可以做得更聰明，比如使用 BitSet。
我無法將您的想法融入這種自上而下（=遞回）的方法。但誰知道呢。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/528341.html
標籤：数组递归
上一篇：如何按特定深度訪問物件條目？