Количество способов допрыгать до n-й позиции (шаги от 1 до k)
n, k = map(int, input().split())
dp = [0] * n
if n == 1:
print(1)
exit()
dp[0] = 1
dp[1] = 1
for i in range(2, min(k + 1, n)):
dp[i] = dp[i - 1] * 2
for i in range(k + 1, n):
dp[i] = dp[i - 1] * 2
dp[i] -= dp[i - k - 1]
print(dp[-1])#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<long long> dp(n);
if (n == 1) {
cout << 1 << endl;
return 0;
}
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i < min(k + 1, n); i++) {
dp[i] = dp[i - 1] * 2;
}
for (int i = k + 1; i < n; i++) {
dp[i] = dp[i - 1] * 2;
dp[i] -= dp[i - k - 1];
}
cout << dp[n - 1] << endl;
return 0;
}Кузнечик находится на позиции 0. За один прыжок он может переместиться вперёд на любое количество позиций от 1 до k. Нужно найти количество способов попасть на позицию n-1 (последняя клетка).
Основная идея динамического программирования:
dp[i] — количество способов попасть на позицию idp[0] = 1 (стартовая позиция)dp[1] = 1 (только прыжок на 1)dp[i] = dp[i-1] * 2 (на позицию i можно попасть прыжком с любой предыдущей позиции)dp[i] = dp[i-1] * 2 - dp[i-k-1] (вычитаем способы, которые пришли с позиции i-k-1, так как прыжок на k+1 отсюда запрещён)Почему формула dp[i] = dp[i-1] * 2 - dp[i-k-1]?
Временная сложность: O(n) — один проход по массиву.
Пространственная сложность: O(n) для массива dp (можно оптимизировать до O(k) с помощью очереди).
Ввод:
n k — количество позиций и максимальная длина прыжкаВывод:
5 2Вывод: 5
Способы для n=5, k=2 (позиции 0..4):
0→1→2→3→4
0→1→2→4
0→1→3→4
0→2→3→4
0→2→4
Всего 5 способов.
5 1Вывод: 1 (только один способ — прыгать на 1)
Введите количество позиций и максимальную длину прыжка: