我正在嘗試解決以下問題（與標題相同）：將陣列劃分為最少數量的子陣列，使每個子陣列的總和在 [w, W] 范圍內，請注意，您不能對陣列重新排序。我想我需要將 DP 與 2D 狀態空間一起使用，但我似乎無法弄清楚。
對此的任何幫助將不勝感激！
uj5u.com熱心網友回復：
一維陣列足以滿足 DP。稱其為 arr，讓 arr[i] 表示僅限于前 i 個元素的同一問題的解決方案。
為 i st 初始化 arr[i] = infinity 直到 & 包括 i 的元素總和是 < w，如果總和 >= w 且 <= W，則為 1。
通過考慮以 i 結尾的所有有效子陣列，在有效子陣列開始之前的最后一個 elt 中獲取所有這些存盤在 arr 中的最小值，并遞增 1，以升序求解 i 的每個未知值。
例如 w=3, W=5, 輸入 = 2,2,3,4,2,1,1,5
initialize: arr = [inf, 1, ...]
input[2]: arr = [inf, 1, 2, ...]
input[3]: arr = [inf, 1, 2, 3, ...]
input[4]: arr = [inf, 1, 2, 3, inf, ...]
input[5]: arr = [inf, 1, 2, 3, inf, 4, ...]
input[6]: arr = [inf, 1, 2, 3, inf, 4, 4, ...]
input[7]: arr = [inf, 1, 2, 3, inf, 4, 4, 5]
解：[2,2], [3], [4], [2,1,1], [5]
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/347349.html
上一篇：洗掉陣列中的重復項，但添加計數屬性以查看重復項的數量
下一篇：編譯時間聯合陣列