讨论/《动态规划精讲(一)》 - 带维度单串 dp[i][k]/
《动态规划精讲(一)》 - 带维度单串 dp[i][k]

dp[i][j] 表示nums[0:i] 切j刀获得的最大平均数和

class Solution {
    public double largestSumOfAverages(int[] A, int K) {
        int n = A.length;
        double[][] dp = new double[n][K];
        // dp[n-1][0] = calcAvg(A,0,n - 1);
        int ret = 0;
        for(int i=0;i<n;i++){
            ret += A[i];
            dp[i][0] = 1.0 * ret / (i + 1);
        }

        for(int i = 1; i< n;i++){
            for(int j = 1; j < K;j++){
                for(int k=0;k<i;k++){
                    dp[i][j] = Math.max(dp[i][j],dp[k][j-1] + calcAvg(A, k+1, i));
                }
            }
        }

        return dp[n-1][K-1];

    }

    public double calcAvg(int[] A,int left,int right){
        int ret = 0;
        for(int i = left;i <= right; i++){
            ret += A[i];
        }
        return 1.0 * ret / (right - left + 1);
    }
}
展开全部 2 讨论