題目：
傳送帶上的包裹必須在 D 天內(nèi)從一個(gè)港口運(yùn)送到另一個(gè)港口斥赋。
傳送帶上的第 i 個(gè)包裹的重量為 weights[i]恼五。每一天痕鳍，我們都會(huì)按給出重量的順序往傳送帶上裝載包裹疲憋。我們裝載的重量不會(huì)超過船的最大運(yùn)載重量。
返回能在 D 天內(nèi)將傳送帶上的所有包裹送達(dá)的船的最低運(yùn)載能力渺尘。
示例 1：
輸入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
輸出：15
解釋：
船舶最低載重 15 就能夠在 5 天內(nèi)送達(dá)所有包裹挫鸽，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10請(qǐng)注意，貨物必須按照給定的順序裝運(yùn)鸥跟，因此使用載重能力為 14 的船舶并將包裝分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允許的丢郊。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有盔沫。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處枫匾。
解答：
方法一：DP
這題一眼就可以看出來可以用遞歸的方法來做架诞，而且可以很快的找到轉(zhuǎn)換關(guān)系，從而想到如何 dp 干茉。
定義 dp(i,j) 是 i 天運(yùn)輸 weights[0-j] 的最低運(yùn)載能力谴忧。
那么可以得到， dp(i,j) = min{ max{ dp(i-1,k) , sum[ k+1 …… j ] } } , 0<=k<j
public int shipWithinDays(int[] weights, int D) {
int[] sum = new int[weights.length];
int[] dp = new int[weights.length];
sum[0] = weights[0];
dp[0] = sum[0];
for (int i = 1; i < weights.length; i++) {
sum[i] = sum[i - 1] + weights[i];
dp[i] = sum[i];
}
for (int i=1;i<D;i++) {
for(int j=weights.length-1;j>i-1;j--) {
for (int k=i-1;k<j;k++) {
dp[j] = Math.min(Math.max(dp[k], sum[j] - sum[k]), dp[j]);
}
}
}
return dp[weights.length-1];
}
btw等脂，這里 dp 枚舉 k 的過程還可以優(yōu)化俏蛮，有興趣的話可以看下四邊形不等式。
方法二：二分法
上面 dp 的方法如果放進(jìn) leetcode 運(yùn)行的話就會(huì)發(fā)現(xiàn) TLE ….
所以換個(gè)思路上遥，定義一個(gè)方法返回 res搏屑，給定一個(gè) limit 變量，遍歷數(shù)組并且進(jìn)行累加粉楚，得到累加和 sum 辣恋。當(dāng) sum 大于 limit 時(shí)，res++模软，sum=當(dāng)前元素伟骨。最后輸出 res 。再將 res 與天數(shù) D 作比較燃异，res 小的話携狭，減小 limit ；res 大的話回俐，增大 limit 逛腿。這里減小和增大可以用二分法進(jìn)行。
public int helper(int[] a, int lim) {
int res = 1;
int sum = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] > lim) {
return Integer.MAX_VALUE;
}
sum += a[i];
if (sum > lim) {
res++;
sum = a[i];
}
}
return res;
}
public int shipWithinDays(int[] weights, int D) {
int maxSum = 0;
int minSum = 0;
for (int i = 0; i < weights.length; i++) {
maxSum += weights[i];
}
while (minSum != maxSum - 1) {
int mid = minSum + (maxSum - minSum) / 2;
if (helper(weights, mid) > D) {
minSum = mid;
} else {
maxSum = mid;
}
}
return maxSum;
}
