這類(lèi)題，dp數(shù)組總長(zhǎng)度要加1纵朋，表示前n個(gè)數(shù)的最優(yōu)值
·1043. Partition Array for Maximum Sum
https://leetcode.com/problems/partition-array-for-maximum-sum/
int maxSumAfterPartitioning(vector<int>& arr, int k) {
int n = arr.size();
vector<int> dp(n+1);
for(int i=1; i<=n; ++i){
int max_num = INT_MIN;
for(int j=1; j<=k && i-j>=0; ++j){
max_num = max(max_num, arr[i-j]);
dp[i] = max(dp[i], dp[i-j] + max_num * j);
}
}
return dp[n];
}
·813. Largest Sum of Averages
https://leetcode.com/problems/largest-sum-of-averages/
double largestSumOfAverages(vector<int>& A, int K) {
int n = A.size();
vector<vector<double>> dp(n+1, vector<double>(K+1, 0.0));
vector<double> sums(n+1, 0.0);
for(int i=1; i<=n; ++i){
sums[i] = sums[i-1] + A[i-1];
dp[i][1] = (double)sums[i] / i;
}
for(int k=2; k<=K; ++k){
for(int i=1; i<=n; ++i){
for(int j=0; j<i; ++j){
dp[i][k] = max(dp[i][k], dp[j][k-1] + (sums[i] - sums[j]) / (i-j));
}
}
}
return dp[n][K];
}
`410. Split Array Largest Sum
https://leetcode.com/problems/split-array-largest-sum/
int splitArray(vector<int>& nums, int m) {
int n = nums.size();
vector<vector<long>> dp(n+1, vector<long>(m+1, INT_MAX));
vector<long> sums(n+1);
for(int i=1; i<=n; ++i){
sums[i] = sums[i-1] + nums[i-1];
}
for(int i=1; i<=n; ++i){
dp[i][1] = sums[i];
}
for(int k=2; k<=m; ++k){
for(int i=1; i<=n; ++i){
for(int j=0; j<i; ++j){
dp[i][k] = min(dp[i][k], max(dp[j][k-1], sums[i] - sums[j]));
}
}
}
return dp[n][m];
}
