Найдите всю последовательную сумму подмножества в O (n ^ 2), используя dp
Вопрос :
Даны n чисел ??,??,…,??, рассмотрим задачу вычисления ?[?,?]=??+??+?⋯?? для всех ?<=?. Наивный алгоритм, вычисляющий каждое ?[?,?] независимо, займет ?(?^?) времени. Найдите эффективный способ решения этой задачи за ?(?^?) времени.
Я попытался нарисовать двухмерную таблицу, в которой строка и столбец равны 1 ~ n, и найти формулу для заполнения всей таблицы (верхний треугольник). Но я думаю, что каждый блок неправильный, может быть, это не очень хорошая идея. Есть идеи? Спасибо.
Ответы 2
Однако нет необходимости в памяти O (n ^ 2). Вы можете использовать так называемые префиксные суммы. Создайте массив 'prefsum[n]', где для каждого i в (1 ... n) prefsum[i] = x1 + x2 + ... + xi. Если вы хотите получить сумму в диапазоне (l, r), просто возьмите prefsum[r] - prefsum[l - 1] (очевидно, если l-1 > 0, иначе ваш результат будет prefsum[r]). Таким образом, вы можете вычислить предварительную сумму за O (n) (простой цикл for) и получить результат для любого диапазона за O (1). Поскольку существует O (n ^ 2) разных диапазонов, ваша сложность равна O (n ^ 2).
Да, ваша идея использовать 2-мерную таблицу (только верхний треугольник) верна. Затем вам нужно только заметить, что:
и что
Таким образом, каждый вход вашей таблицы будет вычисляться за O (1), а весь верхний треугольник за O (n ^ 2)