Подсчет способов представления числа в виде суммы полных квадратов

Опубликовано: 22 Сентября, 2022

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

Примеры:

Input: N = 9
Output: 4
Explanation:
There are four ways to represent 9 as the sum of perfect squares:
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 9
1 + 1 + 1 + 1 + 1 + 4 = 9
1 + 4 + 4 = 9
9 = 9

Input: N = 8
Output: 3

Наивный подход: идея состоит в том, чтобы хранить все идеальные квадраты, меньшие или равные N , в массиве. Теперь проблема сводится к поиску способов суммирования N с использованием элементов массива с разрешенным повторением, которые можно решить с помощью рекурсии. Выполните следующие шаги, чтобы решить проблему:

  • Сохраните все идеальные квадраты меньше или равные N и в массиве psquare[] .
  • Создайте рекурсивную функцию countWays(index, target) , которая принимает два параметра index (изначально N-1). и цель (изначально N):
    • Обработка базовых случаев:
      • Если цель 0, вернуть 1.
      • Если либо индекс, либо цель меньше 0, вернуть 0.
    • В противном случае включите элемент psquare[index] в сумму, вычитая его из цели и рекурсивно вызывая оставшееся значение цели .
    • Исключите элемент psquare[index] из суммы, перейдя к следующему индексу и рекурсивно вызвав то же значение target .
    • Возвращает сумму, полученную путем включения и исключения элемента.
  • В качестве результата выведите значение countWays(N-1, N) .

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

Временная сложность: O( 2K ), где K — количество идеальных квадратов, меньшее или равное N
Вспомогательное пространство: O(1)

Эффективный подход: эта проблема имеет перекрывающиеся подзадачи и свойство оптимальной подструктуры. Чтобы оптимизировать описанный выше подход, идея состоит в том, чтобы использовать динамическое программирование путем запоминания вышеупомянутых рекурсивных вызовов с использованием двумерного массива размера K*N , где K — количество идеальных квадратов, меньшее или равное N .

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

Временная сложность: O(K*N), где K – количество идеальных квадратов, меньшее или равное N.
Вспомогательное пространство: O(K*N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ