🚀 算法題 🚀

🌲 算法刷題專欄 | 面試必備算法 | 面試高頻算法 🍀
🌲 越難的東西,越要努力堅持，因為它具有很高的價值，算法就是這樣?
🌲 作者簡介：碩風和煒，CSDN-Java領域優(yōu)質(zhì)創(chuàng)作者🏆，保研|國家獎學金|高中學習JAVA|大學完善JAVA開發(fā)技術棧|面試刷題|面經(jīng)八股文|經(jīng)驗分享|好用的網(wǎng)站工具分享💎💎💎
🌲 恭喜你發(fā)現(xiàn)一枚寶藏博主,趕快收入囊中吧🌻
🌲 人生如棋，我愿為卒，行動雖慢，可誰曾見我后退一步？🎯🎯

🚀 算法題 🚀

🚩 題目鏈接

• 410. 分割數(shù)組的最大值

? 題目描述

給定一個非負整數(shù)數(shù)組 nums 和一個整數(shù) m ，你需要將這個數(shù)組分成 m 個非空的連續(xù)子數(shù)組。

設計一個算法使得這 m 個子數(shù)組各自和的最大值最小。

示例 1：

輸入：nums = [7,2,5,10,8], m = 2
輸出：18
解釋：
一共有四種方法將 nums 分割為 2 個子數(shù)組。
其中最好的方式是將其分為 [7,2,5] 和 [10,8] 。
因為此時這兩個子數(shù)組各自的和的最大值為18，在所有情況中最小。
示例 2：

輸入：nums = [1,2,3,4,5], m = 2
輸出：9
示例 3：

輸入：nums = [1,4,4], m = 3
輸出：4

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 106
1 <= m <= min(50, nums.length)

🌟 求解思路&實現(xiàn)代碼&運行結果

---

? 暴力法

🥦 求解思路

1. 簡單概括題目的意思:我們需要將給定的數(shù)組nums劃分為k個子數(shù)組，然后找到每一次可以進行劃分方案中的最大值，然后將所有可行的方案中的最小值找出來即可。
2. 怎么做呢？我們就可以枚舉每一個開始的位置i，通過前綴和快速求解從left到i位置子數(shù)組的和，然后遞歸去求后面重復子規(guī)模的結果。
3. 有了基本的思路，接下來我們就來通過代碼來實現(xiàn)一下。

🥦 實現(xiàn)代碼

class Solution {int[] sum;int[] nums;int k;int n;public int splitArray(int[] nums, int k) {this.n=nums.length;this.nums=nums;this.k=k;sum=new int[n+1];for(int i=1;i<=n;i++){sum[i]=sum[i-1]+nums[i-1];}return process(0,0);}public int process(int left,int cnt){if(cnt+1==k){return sum[n]-sum[left]; }int min=Integer.MAX_VALUE;for(int i=left;i<nums.length;i++){int max=Math.max(sum[i+1]-sum[left],process(i+1,cnt+1));min=Math.min(min,max);}return min;}    
}

🥦 運行結果

時間超出了限制，但是不要緊張，這是我們想要的結果！

---

? 記憶化搜索

🥦 求解思路

1. 因為在遞歸的過程中，會重復的出現(xiàn)一些多次計算的結果，我們通過開辟一個數(shù)組，將結果提前緩存下來，算過的直接返回，避免重復計算，通過空間來去換我們的時間。

🥦 實現(xiàn)代碼

class Solution {int[] sum;int[] nums;int k;int[][] dp;int n;public int splitArray(int[] nums, int k) {this.n=nums.length;this.nums=nums;this.k=k;sum=new int[n+1];dp=new int[n+1][k+1];for(int i=0;i<=n;i++) Arrays.fill(dp[i],-1);for(int i=1;i<=n;i++){sum[i]=sum[i-1]+nums[i-1];}return process(0,0);}public int process(int left,int cnt){if(cnt+1==k){return sum[n]-sum[left]; }if(dp[left][cnt]!=-1) return dp[left][cnt];int min=Integer.MAX_VALUE;for(int i=left;i<nums.length;i++){int max=Math.max(sum[i+1]-sum[left],process(i+1,cnt+1));min=Math.min(min,max);}return dp[left][cnt]=min;}    
}

🥦 運行結果

通過緩存，將重復計算的結果緩存下來，通過。
時間情況

空間情況

---

? 動態(tài)規(guī)劃

🥦 求解思路

1. 有了遞歸，有了記憶化搜索，接下來就是動態(tài)規(guī)劃了，直接上手。

🥦 實現(xiàn)代碼

class Solution {int[] sum;int[] nums;int k;int[][] dp;int n;public int splitArray(int[] nums, int k) {this.n=nums.length;this.nums=nums;this.k=k;sum=new int[n+1];dp=new int[n+1][k+1];for(int i=1;i<=n;i++){sum[i]=sum[i-1]+nums[i-1];}for(int i = 0; i <= n; i++){Arrays.fill(dp[i], Integer.MAX_VALUE);}dp[n][k]=0;for(int left=n-1;left>=0;left--){for(int cnt=k-1;cnt>=0;cnt--){int min=Integer.MAX_VALUE;for(int i=left;i<n;i++){int max=Math.max(sum[i+1]-sum[left],dp[i+1][cnt+1]);min=Math.min(min,max);}dp[left][cnt]=min;}}return dp[0][0];} 
}

🥦 運行結果

動態(tài)規(guī)劃搞定，大家可以積極的嘗試。

時間復雜度

空間復雜度

---

💬 共勉

最后，我想和大家分享一句一直激勵我的座右銘，希望可以與大家共勉！