สมมติว่าเราแบ่งแถวของตัวเลข A ออกเป็น K กลุ่มที่อยู่ติดกันมากที่สุด จากนั้นเราจะกำหนดคะแนนเป็นผลรวมของค่าเฉลี่ยของแต่ละกลุ่ม เราต้องพบว่าอะไรคือคะแนนสูงสุดที่เราจะทำได้ สมมติว่า A =[9,1,2,3,9] และ K คือ 3 ผลลัพธ์จะเป็น 20 เนื่องจากตัวเลือกที่ดีที่สุดคือการแบ่ง A เป็น [9], [1, 2, 3] [9]. คำตอบคือ 9 + (1 + 2 + 3) / 3 + 9 =20 เราอาจแบ่ง A ออกเป็น [9, 1], [2], [3, 9],
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดเมทริกซ์ dp
- กำหนดวิธีการแบบเรียกซ้ำแก้ปัญหา () ซึ่งจะใช้อาร์เรย์ A ดัชนีและ k
- ถ้า index>=size ของ A ให้คืนค่า 0
- ถ้า k เป็น 0 ให้คืนค่า -100000
- ถ้า dp[index, k] ไม่ใช่ – 1 ให้คืนค่า dp[index, k]
- ret :=-inf และ sum :=0
- สำหรับฉันอยู่ในช่วงดัชนีถึงขนาด A – 1
- sum :=sum + A[i]
- ret :=สูงสุดของ ret และ sum/(i – ดัชนี + 1) + แก้ (A, i + 1, k – 1)
- set dp[index, k] :=ret and return.
- จากวิธีหลัก ให้ทำดังต่อไปนี้ −
- n :=ขนาดของ A
- dp :=เมทริกซ์ n x (K + 1) เติมด้วย – 1
- ผลตอบแทนแก้(A, 0, K)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector < vector <double> > dp;
double solve(vector <int>& A, int idx, int k){
if(idx >= A.size()) return 0;
if(!k) return -100000;
if(dp[idx][k] != -1) return dp[idx][k];
double ret = INT_MIN;
double sum = 0;
for(int i = idx; i < A.size(); i++){
sum += A[i];
ret = max(sum / (i - idx + 1) + solve(A, i + 1, k - 1), ret);
}
return dp[idx][k] = ret;
}
double largestSumOfAverages(vector<int>& A, int K) {
int n = A.size();
dp = vector < vector <double> > (n, vector <double>(K + 1, -1));
return solve(A, 0, K);
}
};
main(){
vector<int> v = {9,1,2,3,9};
Solution ob;
cout << (ob.largestSumOfAverages(v, 3));
} อินพุต
[9,1,2,3,9] 3
ผลลัพธ์
20
