C++描述 LeetCode 1770. 執行乘法運算的最大分數
??大家好，我叫亓官劼（qí guān jié ），在CSDN中記錄學習的點滴歷程，時光荏苒，未來可期，加油~博主目前僅在CSDN中寫博客，唯一博客更新的地址為：亓官劼的博客 ，同時正在嘗試在B站中做一些內容分享，B站主頁為： 亓官劼的B站主頁
本文原創為亓官劼，請大家支持原創，部分平臺一直在惡意盜取博主的文章！！！
若需聯系博主，可以聯系本人微信：qiguanjie2015
給你兩個長度分別 n 和 m 的整數陣列 nums 和 multipliers ，其中 n >= m ，陣列下標 從 1 開始 計數，
初始時，你的分數為 0 ，你需要執行恰好 m 步操作，在第 i 步操作（從 1 開始 計數）中，需要：
- 選擇陣列
nums開頭處或者末尾處 的整數x， - 你獲得
multipliers[i] * x分，并累加到你的分數中， - 將
x從陣列nums中移除，
在執行 m 步操作后，回傳 最大 分數*，*
示例 1：
輸入：nums = [1,2,3], multipliers = [3,2,1]
輸出：14
解釋：一種最優解決方案如下：
- 選擇末尾處的整數 3 ，[1,2,3] ，得 3 * 3 = 9 分，累加到分數中，
- 選擇末尾處的整數 2 ，[1,2] ，得 2 * 2 = 4 分，累加到分數中，
- 選擇末尾處的整數 1 ，[1] ，得 1 * 1 = 1 分，累加到分數中，
總分數為 9 + 4 + 1 = 14 ，
示例 2：
輸入：nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
輸出：102
解釋：一種最優解決方案如下：
- 選擇開頭處的整數 -5 ，[-5,-3,-3,-2,7,1] ，得 -5 * -10 = 50 分，累加到分數中，
- 選擇開頭處的整數 -3 ，[-3,-3,-2,7,1] ，得 -3 * -5 = 15 分，累加到分數中，
- 選擇開頭處的整數 -3 ，[-3,-2,7,1] ，得 -3 * 3 = -9 分，累加到分數中，
- 選擇末尾處的整數 1 ，[-2,7,1] ，得 1 * 4 = 4 分，累加到分數中，
- 選擇末尾處的整數 7 ，[-2,7] ，得 7 * 6 = 42 分，累加到分數中，
總分數為 50 + 15 - 9 + 4 + 42 = 102 ，
提示：
n == nums.lengthm == multipliers.length1 <= m <= 103- `m <= n <= 105```
-1000 <= nums[i], multipliers[i] <= 1000
解題思路
區間dp，在計算之前，我們可以先簡化nums的長度，因為我們只能在兩邊進行洗掉，所以我們只要在兩邊各保留m個即可，然后對當前的區間進行區間dp，遍歷區間長度為 n-m+1 到n的情況，
演算法實作
class Solution {
public:
int maximumScore(vector<int>& nums, vector<int>& multipliers) {
int n = nums.size(), m = multipliers.size();
if(n >= m*2){
// 因為只能刪兩端，中間多余的時沒用的，所以可以將中間的部分洗掉，兩端各留N個即可
int x = m, y = n-m;
while(y < n)
nums[x++] = nums[y++];
n = x;
}
vector<vector<int>> dp(n+10,vector<int>(n+10));
// 區間DP
for(int len = n-m+1; len <= n; len++){
// 遍歷區間長度為 n-m+1 到n的情況
// i為左端點，j為右端點
for(int i = 1; i + len -1 <= n ; i++){
int j = i + len -1;
dp[i][j] = max(dp[i+1][j] + nums[i-1]*multipliers[n-len],dp[i][j-1]+nums[j-1]*multipliers[n-len]);
}
}
return dp[1][n];
}
};
亓官劼
CSDN認證博客專家
Python
全堆疊
資料結構與演算法
CSDN認證博客專家
Python
全堆疊
資料結構與演算法
大家好，我是亓官劼(qí guān jié)，在博客中分享資料結構與演算法、Python全堆疊開發、Java后端開發、前端、OJ題解及各類報錯資訊解決方案等經驗，一起加油，用知識改變命運，未來可期，若有事項需聯系博主，可通過微信：qiguanjie2015 進行聯系，有慷訓回復，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/263371.html
標籤：其他