Array Partition (k groups) for S

这类题，dp数组总长度要加1，表示前n个数的最优值

·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];
    }