Голос Google Интервью

Question

Учитывая, что каждый кубик «a» и сумма b возвращают количество способов, в которых может быть получена сумма b. Как уменьшить временную сложность и сложность пространства? Это было задано в интервью Google, и я не уверен в ответе.

Answer 1

Предполагая достаточно большой (для определенности а> = б-п), это сводится к

x1+x2+x3+...+xn=b 

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

(y1+1)+(y2+1)...+(yn+1)=b 
y1+y2+...+yn=b-n 

поэтому общее решение z1 + z2 + ... гк = п С (п + к-1, k- 1)

EDIT после reciving несколько downvotes:

Предположим, что мы имеем ограничение на 'а' т млрд> а, мы можем сформулировать это как проблему DP, где

dp[k][j] is no. of ways to get a sum of j using dices 1 to k inclusive 
dp[1][j] is 0 if j>a or j==0 else 1 

, то мы можем иметь оценку следующие соотношения

from k = 2 to n 
    from j = 1 to b 
    from x = 1 to a 
     dp[k][j] += dp[k-1][j-x] where x is from 1 to a at max and x<j 

и ответ должен быть дп [п] [б] Хранение, если порядок п * б и выполнения О (п * б * а)

Answer 2

Это просит вас найти количество способов написать b в виде суммы n положительных целых чисел. Ответ - это номер compositions от b до n деталей, которые составляют (b-1 choose n-1).

Теперь, если учесть ограничение того, что размер деталей ограничен a, проблема становится немного интереснее. Я рекомендую использовать для этого generating functions. Ответом будет коэффициент x^b в продукте (x+x^2+...+x^a)^n. Зачем? Потому что для каждой матрицы (единственного числа костей) у вас есть число между 1 и a, и это представлено показателем x. Когда вы берете один x^i от каждого из условий n, это эквивалентно числу i, приходящему на эту матрицу. Сумма показателей должна быть суммой, которую вы после, а именно b.

Мы даже можем упростить проблему немного с помощью multinomial theorem, который гласит:

(x + x^2 + ... + x^a)^n = sum_{k1+k2+...+ka=n} (n multichoose k1,k2,...,ka) x^{k1+2*k2+...+a*ka} 

где все ki >= 0. Таким образом, ответ в том, что число способов является

sum_{k1+k2+...+ka=n & k1+2*k2+...+a*ka=b} (n multichoose k1,k2,...,ka) 

Answer 3

Я бы массив hits[max + 1], который подсчитывает количество возможных комбинаций для каждого значения. max - n * a и, конечно, hits[0] - hits[n - 1] останется пустым.

Глупым способом было бы сделать n для цикла (по одному для каждой матрицы) и зарегистрировать хит в hits для текущей суммы кубиков.

Чем меньше немой способ заключается в использовании немного комбинаторики, где я выписывать число комбинаций для каждого заказал перетасовки:

есть 1 комбинация 1111 (сумма = 4)
есть 4 комбинации 1112 (суммы = 5)
есть 4 комбинации 1113 (суммы = 6)
...
есть 4 * 3/2 комбинации 1123 (суммы = 7)
...
есть 4 * 3 * 2 ком Гиббса, 1234 (сумма = 10)
...
есть 1 комбинация aaaa (сумма = n * a)

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

Эти петли только перемещают (n - 1) разделение разделов на (1, 2, 3, 4, ..., a). Разделения могут находиться в одном и том же месте (например, все они между 1 и 2 для корпуса 1111), но вы не должны иметь разделение ниже 1 или выше a.