Наибольшая сумма средних: преобразовать базовый код в DP с минимальными изменениями (убедившись, что новый код также возвращается)

Question

Постановка задачи: мы разбиваем ряд чисел A на не более K смежных (непустых) групп, тогда наша оценка является суммой среднего значения для каждой группы. Какую наибольшую оценку мы можем получить?

Обратите внимание, что наш раздел должен использовать каждое число в A, и что оценки не обязательно являются целыми числами. Пример: Вход: 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], например. Этот раздел приведет к 5 + 2 + 6 = 13, что еще хуже.

Как сделать следующий код обратного отслеживания для dp с минимальными изменениями. При запуске грубой силы он работает, но дает TLE. Я предпочитаю возврат с помощью dp, потому что он более интуитивен для меня.

class Solution {
public:

    double Util(vector<int>& A ,int no_of_groups_left, int index, double avg){

        if(no_of_groups_left >= 0 && index > A.size()-1 ) return avg;
        if(index > A.size()-1) return 0.0;
        if(no_of_groups_left < 0) return 0.0;


        double sum =0.0 , count = 1.0 , cur_avg = 0.00 , mx = -100000.0;
        for(int i = index; i<A.size(); i++){
            sum+= (double)A[i]; count = i-index+1;
            cur_avg = sum/count;
            mx = max(mx , Util(A,no_of_groups_left-1,i+1,cur_avg+avg));
        }

        return mx;
    }

    double largestSumOfAverages(vector<int>& A, int K) {


        double sum =0.0 , count = 1 , cur_avg = 0.00 , mx = -100000.0;
        for(int i = 0; i<A.size(); i++){
            sum+= A[i]; count = i+1;
            cur_avg = sum/count;
            mx = max(mx , Util(A,K-1,i+1,cur_avg));
        }
        return mx;
    }
};