Динамическое программирование пирамид

Ответ 1

Выберем подходящее определение:

f(n, m) = # pyramids out of n bricks with base of size < m

Ответ, который вы ищете сейчас (учитывая, что N - ваше количество входных блоков):

f(N, N+1) - 1

Позвольте сломать это:

• Первый N очевиден: количество ваших кирпичей.
• Ваша нижняя строка будет содержать не более N кирпичей (потому что это все, что у вас есть), поэтому N+1 является достаточной нижней границей.
• Наконец, - 1 существует, потому что технически пустая пирамида также является пирамидой (и, следовательно, будет учитываться), но вы исключаете ее из своих решений.

Базовые случаи просты:

f(n, 0) = 1   for any n >= 0
f(0, m) = 1   for any m >= 0

В обоих случаях это пустая пирамида, которую мы здесь подсчитываем.

Теперь все, что нам нужно, это рекурсивная формула для общего случая.

Предположим, что нам даны N и m и выберите кирпичи i на нижнем слое. Что мы можем разместить поверх этого слоя? Меньшая пирамида, для которой у нас есть n - i кирпичи слева и основание которых имеет размер < i. Это точно f(n - i, i).

Каков диапазон для i? Мы можем выбрать пустую строку так i >= 0. Очевидно, i <= n, потому что мы имеем только кирпичи N. Но также, i <= m - 1, по определению m.

Это приводит к рекурсивному выражению:

f(n, m) = sum f(n - i, i) for 0 <= i <= min(n, m - 1)

Вы можете вычислить f рекурсивно, но с помощью динамического программирования это будет быстрее, конечно. Однако сохранение матрицы результатов является простым, поэтому я оставляю это до вас.

Возвращаясь к первоначальному утверждению, что f(N, N+1)-1 - это ответ, который вы ищете, на самом деле не имеет значения, какое значение выбрать для m, пока оно > N. На основе рекурсивной формулы легко показать, что f(N, N + 1) = f(N, N + k) для каждого k >= 1:

f(N, N + k) = sum f(N - i, i) for 0 <= i <= min(N, N + k - 1)
            = sum f(N - i, i) for 0 <= i <= N
            = sum f(N - i, i) for 0 <= i <= min(N, N + 1 - 1)

Ответ 2

Сколько способов вы можете построить пирамиду ширины n? Помещая любую пирамиду шириной n-1 или меньше где-нибудь поверх слоя n кирпичей. Поэтому, если p (n) - число пирамид с шириной n, то p (n) = sum [m = 1 to n-1] (p (m) * c (n, m)), где c (n, m) - это количество способов размещения слоя ширины m на слое ширины n (я надеюсь, что вы можете работать с этим самим).

Это, однако, не ограничивает количество кирпичей. Как правило, в DP любое ограничение ресурсов должно быть смоделировано как отдельное измерение. Итак, ваша проблема теперь p (n, b): "Сколько пирамид вы можете построить шириной n с общим количеством b кирпичей"? В рекурсивной формуле для каждого возможного способа построения меньшей пирамиды на вашей текущей, вам нужно обратиться к правильному количеству оставшихся кирпичей. Я оставляю это как вызов для выработки рекурсивной формулы; сообщите мне, если вам нужны какие-либо подсказки.

Ответ 3

Вы можете подумать о своей рекурсии как: при условии x оставшихся кирпичей, где вы использовали кирпичи n в последней строке, сколько пирамид вы можете построить. Теперь вы можете заполнить строки из верхней или нижней строки или от нижней до верхней строки. Я объясню первый случай.
Здесь рекурсия может выглядеть примерно так (left - количество оставшихся кирпичей и last - количество кирпичей, используемых в последней строке)

f(left,last)=sum (1+f(left-i,i)) for i in range [last+1,left] inclusive.

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

код:

int calc(int left, int last) {
    int total=0;
    if(left<=0) return 0;  // terminal case, no pyramid with no brick
    for(int i=last+1; i<=left; i++) {
        total+=1+calc(left-i,i);
    }
    return total;
}

Я оставлю это вам для реализации версии memoized или bottom-up dp. Также вы можете начать с нижней строки и заполнить верхние строки в пирамиде.

Ответ 4

Поскольку нас просят считать пирамиды любой мощности, меньшей или равной n, мы можем рассмотреть каждую мощность в свою очередь (пирамиды 1 элемента, 2 элемента, 3... и т.д.) и суммировать их. Но как много разных способов мы можем составить пирамиду из элементов k? Тот же номер, что и число различных разделов k (например, для k = 6, мы можем иметь (6), (1,5), (2,4), and (1,2,3)). Генерирующая функция/рекурсия для подсчета различных разделов описана в Wikipedia и последовательность в OEIS.

Повторение, основанное на Пятиугольное число Теорема:

q(k) = ak + q(k − 1) + q(k − 2) − q(k − 5) − q(k − 7) + q(k − 12) + q(k − 15) − q(k − 22)...
  where ak is (−1)^(abs(m)) if k = 3*m^2 − m for some integer m and is 0 otherwise.

(The subtracted coefficients are generalized pentagonal numbers.)

Поскольку повторяемость, описанная в Википедии, обязывает вычисление всех предыдущих q(n) для достижения большего q(n), мы можем просто суммировать результаты на пути к получению нашего результата.

Код JavaScript:

function numPyramids(n){

  var distinctPartitions = [1,1],
      pentagonals = {},
      m = _m = 1,
      pentagonal_m = 2,
      result = 1;

  while (pentagonal_m / 2 <= n){
    pentagonals[pentagonal_m] = Math.abs(_m);
    m++;
    _m = m % 2 == 0 ? -m / 2 : Math.ceil(m / 2);
    pentagonal_m = _m * (3 * _m - 1);
  }

  for (var k=2; k<=n; k++){
    distinctPartitions[k] = pentagonals[k] ? Math.pow(-1,pentagonals[k]) : 0;
    var cs = [1,1,-1,-1],
        c = 0;
    for (var i in pentagonals){
      if (i / 2 > k)
        break;
      distinctPartitions[k] += cs[c]*distinctPartitions[k - i / 2];
      c = c == 3 ? 0 : c + 1;
    }
    result += distinctPartitions[k];
  }
  return result;
}

console.log(numPyramids(6)); // 13