410. 分割數組的最大值preface題目與解法總結
雖然說微信的公眾號有些Σ(☉▽☉"a，我純複製markdown的內容居然不太行，實在做的太爛了（不是。
今天的內容，或者說每日一題也是實在變態，一看到就直接翻翻答案找找思路這樣o(╥﹏╥)o，話不多說進入正題。今天的內容依然是動歸主題。
題目與解法給定一個非負整數數組和一個整數 m，你需要將這個數組分成 m 個非空的連續子數組。設計一個算法使得這 m 個子數組各自和的最大值最小。
注意:數組長度 n 滿足以下條件:
1 ≤ n ≤ 10001 ≤ m ≤ min(50, n)示例:
輸入:nums = [7,2,5,10,8]m = 2
輸出:18
解釋:一共有四種方法將nums分割為2個子數組。其中最好的方式是將其分為[7,2,5] 和 [10,8]，因為此時這兩個子數組各自的和的最大值為18，在所有情況中最小。
來源：力扣（LeetCode）連結：
https://leetcode-cn.com/problems/split-array-largest-sum
著作權歸領扣網絡所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
一看到這，直接推，翻閱答案，沒想到你這濃眉大眼的也是用動歸？
仔細閱讀題目，那麼可以知道我們有n個數字，m個組，並且，假設有變量k表示前k個數字被分為m - 1組與剩下的數值之和之間最大值就是就是當前分組狀態下所取的值。所以我們只要遍歷從k 到 n求最小值即可算出所求n個數字， m個分組的最優值。又因為n，m都與前面的數值有關，所以需要遍歷兩次n， 一次m。
話不多說，先看代碼
#include <iostream>#include <vector>#include <algorithm>using namespace std;
class Solution {public: int splitArray(vector<int>& nums, int m) { const auto n = static_cast<int>(nums.size()); vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, LLONG_MAX)); vector<long long> sub(n + 1, 0); for (auto i = 0; i < n; ++i) { sub[i + 1] = sub[i] + nums[i]; } dp[0][0] = 0; for (auto i = 1; i <= n; ++i) { for (auto j = 1; j <= min(i, m); ++j) { for (auto k = 0; k < i; ++k) { dp[i][j] = min(dp[i][j], max(dp[k][j - 1], sub[i] - sub[k])); } } } return static_cast<int>(dp[n][m]); }};
int main(){ vector<int> vec{ 7, 2, 5, 10, 8 }; Solution s; cout << s.splitArray(vec, 2); return 0;}當然了，我前一篇文章說過，動歸通常不是最優解，因為他會無限接近暴力法的方式。
我們再仔細看看題目，似乎我們可以設定一個上下限，然後不斷迫近最優值。也就是說，最低值只可能是分出一個，然後這個值是nums裡面的最大值，最大值也只有m為一時，所有數組加起來的值，那麼我們只有不斷折半查找其中的值即可。那麼，驗證這種對半的說產生的值的方法是我們在這nums總能找到不大於m的分組，這樣一來，我們就可以知道至少這個值可以是新的上界，如若不然，則一定是新的下界。為了打破這種循環，我們算出的下界加一即可。
#include <iostream>#include <vector>using namespace std;
class Solution {public: int splitArray(vector<int>& nums, int m) { auto check = [&nums](const int x,const int m) { long long sum = 0; auto cnt = 1; for (auto i = static_cast<size_t>(0); i < nums.size(); ++i) { if (sum + nums[i] > x) { ++cnt; sum = nums[i]; } else { sum += nums[i]; } } return cnt <= m; }; long long lhv = 0, rhv = 0; for (auto i = static_cast<size_t>(0); i < nums.size(); ++i) { rhv += nums[i]; if (lhv < nums[i]) { lhv = nums[i]; } } while (lhv < rhv) { const auto mid = lhv + ((rhv - lhv) >> 1); if (check(mid, m)) { rhv = mid; } else { lhv = mid + 1; } } return static_cast<int>(lhv); }};
int main(){ vector<int> vec{ 7, 2, 5, 10, 8 }; Solution s; cout << s.splitArray(vec, 2);
return 0;}
總結
還是看題解大法好~