Подсчитайте способы разбить массив на подмассивы так, чтобы сумма i-го подмассива делилась на i

Дан массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы найти количество способов разбить массив на непустые подмассивы так, чтобы сумма i ^-го подмассива делилась на i .

Примеры:

Input: arr[] = {1, 2, 3, 4}
Output: 3
Explanation:
Following are the number of ways to split the array into non-empty subarray as:

1. Split the array into subarray as {1}, {2}, {3}, {4} and the sum of each of the ith subarray is divisible by i.
2. Split the array into subarray as {1, 2, 3}, {4} and each of the ith subarray is divisible by i.
3. Split the array into subarray as {1, 2, 3, 4} and each of the ith subarray is divisible by i.

As there are only 3 possible ways to split the given array. Therefore, print 3.

Input: arr[ ] = {1, 1, 1, 1, 1}
Output: 3

Подход: Данную проблему можно решить с помощью динамического программирования, поскольку она имеет перекрывающиеся подзадачи и оптимальную подструктуру. Подзадачи можно хранить в таблице dp[][] с помощью мемоизации, где dp[i][j] хранит количество разделов до i -го индекса arr[] в j -м непустом подмассиве. Эту идею можно реализовать с помощью массива Prefix Sum pre[] , в котором хранится сумма всех элементов до каждого i ^-го индекса, а dp[i][j] можно вычислить как сумму dp[k][j – 1] для все значения k < i такие, что (pre[i] – pre[k]) кратно j . Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте переменную, скажем, count , в которой хранится количество возможных разбиений данного массива на подмассивы.
• Найдите сумму префиксов массива и сохраните ее в другом массиве, скажем, prefix[] .
• Инициализируйте двумерный массив, скажем, dp[][] , который хранит все перекрывающиеся состояния dp[i][j] .
• Переберите диапазон [0, N], используя переменную i , и вложенный перебор диапазона [N, 0], используя переменную j , и выполните следующие шаги:
  1. Увеличьте значение dp[j + 1][pre[i + 1] % (j + 1)] на значение dp[j][pre[i + 1] % j] , так как это обозначает количество разделов до индекс i в j непрерывную подпоследовательность, кратную (j + 1) .
  2. Если значение i равно (N – 1) , затем обновите значение count на dp[j][pre[i + 1] % j] .
• После выполнения вышеуказанных шагов выведите в качестве результата значение count .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: O(N ² )