813. Largest Sum of Averages

https://leetcode.com/problems/largest-sum-of-averages/description/

解题思路：

1. 用深度搜索方法：when k = 1 是返回条件, 截枝条件为dp[startindex][k] ！= 0

代码：
class Solution {
int len = 0;
public double largestSumOfAverages(int[] A, int K) {

    len = A.length;
    double[] sum = new double[len];
    sum[0] = A[0];
    for(int i = 1; i < len; i++)
        sum[i] = sum[i-1] + A[i];
    return dfs(A, K, 0, new double[len][K + 1], sum);
}
public double dfs(int[] A, int k, int startIndex, double[][] dp, double[] sum){
    if(k == 1) return (sum[len - 1] - sum[startIndex] + A[startIndex]) / (len - startIndex);
    if(dp[startIndex][k] != 0) return dp[startIndex][k];
    for(int i = startIndex; i <= len - k; i++){
        dp[startIndex][k] = Math.max(dp[startIndex][k], (sum[i] - sum[startIndex] + A[startIndex]) * 1.0 / (i - startIndex +1) + dfs(A, k-1, i+1, dp, sum));
    }
    return dp[startIndex][k];
}

}