🚀 算法題 🚀

🌲 算法刷題專欄 | 面試必備算法 | 面試高頻算法 🍀
🌲 越難的東西,越要努力堅(jiān)持，因?yàn)樗哂泻芨叩膬r(jià)值，算法就是這樣?
🌲 作者簡(jiǎn)介：碩風(fēng)和煒，CSDN-Java領(lǐng)域新星創(chuàng)作者🏆，保研|國(guó)家獎(jiǎng)學(xué)金|高中學(xué)習(xí)JAVA|大學(xué)完善JAVA開(kāi)發(fā)技術(shù)棧|面試刷題|面經(jīng)八股文|經(jīng)驗(yàn)分享|好用的網(wǎng)站工具分享💎💎💎
🌲 恭喜你發(fā)現(xiàn)一枚寶藏博主,趕快收入囊中吧🌻
🌲 人生如棋，我愿為卒，行動(dòng)雖慢，可誰(shuí)曾見(jiàn)我后退一步？🎯🎯

🚀 算法題 🚀

🚩 題目鏈接

• 1402. 做菜順序

? 題目描述

一個(gè)廚師收集了他 n 道菜的滿意程度 satisfaction ，這個(gè)廚師做出每道菜的時(shí)間都是 1 單位時(shí)間。

一道菜的 「 like-time 系數(shù) 」定義為烹飪這道菜結(jié)束的時(shí)間（包含之前每道菜所花費(fèi)的時(shí)間）乘以這道菜的滿意程度，也就是 time[i]*satisfaction[i] 。

返回廚師在準(zhǔn)備了一定數(shù)量的菜肴后可以獲得的最大 like-time 系數(shù) 總和。

你可以按 任意 順序安排做菜的順序，你也可以選擇放棄做某些菜來(lái)獲得更大的總和。

示例 1：

輸入：satisfaction = [-1,-8,0,5,-9]
輸出：14
解釋：去掉第二道和最后一道菜，最大的 like-time 系數(shù)和為 (-11 + 02 + 5*3 = 14) 。每道菜都需要花費(fèi) 1 單位時(shí)間完成。
示例 2：

輸入：satisfaction = [4,3,2]
輸出：20
解釋：可以按照任意順序做菜 (21 + 32 + 4*3 = 20)
示例 3：

輸入：satisfaction = [-1,-4,-5]
輸出：0
解釋：大家都不喜歡這些菜，所以不做任何菜就可以獲得最大的 like-time 系數(shù)。

提示：

n == satisfaction.length
1 <= n <= 500
-1000 <= satisfaction[i] <= 1000

🌟 求解思路&實(shí)現(xiàn)代碼&運(yùn)行結(jié)果

---

? 動(dòng)態(tài)規(guī)劃 + 貪心

🥦 求解思路

1. 通過(guò)理解題目的意思，我們首先知道，可以以任意順序做菜，其次，我們舉幾個(gè)例子就會(huì)發(fā)現(xiàn)，如果想要最后的結(jié)果大，可以把滿意程度大的放到最后來(lái)完成。
2. 為什么呢？一方面是數(shù)組中的元素本身就大，另外一方面，放到最后，時(shí)間也會(huì)很長(zhǎng)。如果我們想要最后的結(jié)果很大，與這倆個(gè)變量又密切的關(guān)系。
3. 其次，就是我們的動(dòng)態(tài)規(guī)劃，該題目的原型是0-1背包模型。不會(huì)的同學(xué)可以看看，此處不做過(guò)多的講解。
4. 具體求解的過(guò)程步驟請(qǐng)看下面代碼。

🥦 實(shí)現(xiàn)代碼 - 緩存

class Solution {int[][] dp;public int maxSatisfaction(int[] satisfaction) {Arrays.sort(satisfaction);int n=satisfaction.length;dp=new int[n+1][n+1];for(int i=0;i<=n;i++){Arrays.fill(dp[i],-1);}return process(0,0,satisfaction);}public int process(int i,int cnt,int[] satisfaction){if(i>=satisfaction.length){return 0;}if(dp[i][cnt]!=-1) return dp[i][cnt];int p1=0,p2=0;for(int j=0;j<=i;j++){p1=process(i+1,cnt+1,satisfaction)+(cnt+1)*satisfaction[j];p2=process(i+1,cnt,satisfaction);}return dp[i][cnt]=Math.max(p1,p2);}
}

🥦 運(yùn)行結(jié)果

🥦 實(shí)現(xiàn)代碼 - 動(dòng)態(tài)規(guī)劃

class Solution {int[][] dp;public int maxSatisfaction(int[] satisfaction) {Arrays.sort(satisfaction);int n=satisfaction.length;dp=new int[n+1][n+1];for(int i=0;i<=n;i++){dp[n][i]=0;}  for(int i=n-1;i>=0;i--){int p1=0,p2=0;for(int cnt=n-1;cnt>=0;cnt--){p1=dp[i+1][cnt+1]+(cnt+1)*satisfaction[i];p2=dp[i+1][cnt];dp[i][cnt]=Math.max(p1,p2);}}return dp[0][0];}
}

🥦 運(yùn)行結(jié)果

---

💬 共勉

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