В тази публикация ще обсъдим leetcode 1155 — брой хвърляния на зарове с целева сума, който се задава в интервюта на Microsoft и Amazon.

Анализ на проблема

Имате n зарчета и всеки зар има k лица, номерирани от 1 до k.

Дадени са три цели числа n, k и target, върнетеброя на възможните начини (от kn общо начина) за хвърляне на заровете, така че сборът от числата с лицето нагоре да е равен на target. Тъй като отговорът може да е твърде голям, върнете го по модул 109 + 7.