Мистер Фокс разрабатывает программу для робота-лунохода. Сегодня его роботу нужно добраться по прямой дороге длиной 20 футов от космодрома до базы, попутно забрав ценный предмет. Будем считать дорогу отрезком, в левом конце которого находится космодром, в правом конце – база, а ровно посередине – лежит ценный предмет. Мистер Фокс может давать роботу три команды: A – сместиться на 1 фут вправо, B – сместиться на 2 фута вправо, C – сместиться на 3 фута вправо. Набор из 20 футов команд A является удачным, так как приводит робота на базу (попутно он заберет ценный предмет, потому что остановится около него), а вот набор BCCCCCC удачным не является: робота на базу он приведет, но вот ценный предмет робот не заберет, поскольку не остановится около него. Сколько существует удачных наборов команд?
Для решения этой задачи можно воспользоваться динамическим программированием. Обозначим dp[i] как количество способов добраться до i-го фута дороги. Имеем начальные условия dp[0] = 1 (робот уже на космодроме) и dp[1] = 0 (не можем оказаться на 1-м футе прямо на ценном предмете).
Далее для каждого i от 0 до 20 посчитаем dp[i] по формуле dp[i] = dp[i-1] + dp[i-2] + dp[i-3].
Таким образом, количество удачных наборов команд будет равно dp[20]. В итоге получаем, что количество удачных наборов команд равно 121415.
Для решения этой задачи можно воспользоваться динамическим программированием. Обозначим dp[i] как количество способов добраться до i-го фута дороги. Имеем начальные условия dp[0] = 1 (робот уже на космодроме) и dp[1] = 0 (не можем оказаться на 1-м футе прямо на ценном предмете).
Далее для каждого i от 0 до 20 посчитаем dp[i] по формуле
dp[i] = dp[i-1] + dp[i-2] + dp[i-3].
Таким образом, количество удачных наборов команд будет равно dp[20]. В итоге получаем, что количество удачных наборов команд равно 121415.