Основы программирования

Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K. Найти число различных путей, по которым фишка может пройти поле от начала до конца.
Пример. N=3, K=2
Возможные пути:
1,1,1
1,2
2,1
Ответ: 3.

Очевидное решение задачи предполагает разложение числа N на всевозможные суммы таким образом, чтобы каждое слагаемое в сумме не превосходило k. Очевидно, что таких разложений очень много, особенно если учитывать, порядок слагаемых в разложении существенен, так как он соответствует различной последовательности ходов фишки.
Обозначим через S(i) количество различных путей, по которым фишка может пройти поле от начала до позиции с номером i. Предположим теперь, что для любого j от 1 до i известны значения величин S(j). Задача состоит в определении правила вычисления значения S(i+1), используя значения известных величин. Легко заметить, что в позицию с номером i+1 фишка может попасть из позиций i, i-1,...,i-k. Следовательно,
S(i+1)=S(i)+S(i-1)+...+S(i-k).
Таким образом, вычисляя последовательно значения величин S(1), S(2),..., S(N) по описанному выше правилу, получаем значение S(N), которое и указывает общее количество различных путей, по которым фишка может пройти поле от начала до позиции с номером N.

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
 
int findways(int, int);
 
int main(void)
{
	int
		n,
		k;
 
	puts("Please input positive integer n and k...");
	scanf("%d %d", &n, &k);
 
	printf("%d way(s)", findways(n, k));
 
    return 0;
}
 
 
 
int findways(int n, int k)
{
	int
		i,
		j,
		nways,
		*s = (int *)calloc(n + 1, sizeof(int));
 
	memset(s, 0, n + 1); /* инициализация массива нулями */
 
	/* базовые случаи для которых считать ничего не надо */
	s[0] = 1;
	s[1] = 1;
 
	if (k <= 1 || n <= 0)
		return 1;
	else
		for (i = 2; i < n + 1; i++)
			/* количество путей для данного i равно сумме количеств путей
			   для k предыдущих i или для всех i, если i - k < 0 */
			for ((i - k < 0) ? (j = 0) : (j = i - k); j < i; j++)
				s[i] += s[j];
 
	nways = s[n];
	free(s);
 
	return nways;
}