Задача динамического программирования (acmp 169)

[Константин01]

Здравствуйте!

Прошу помощи в решение задачи. Условие:

На расстоянии N шагов от магазина стоит человек. Каждую минуту он выбирает, куда сделать шаг: к магазину или в противоположном направлении.

Требуется написать программу, которая определит, сколькими способами он может попасть в магазин, пройдя ровно K шагов и оказавшись в магазине только после выполнения последнего шага.

Входные данные
Входной файл INPUT.TXT содержит 2 числа n и k, записанные через пробел. Известно, что 1 ≤ N ≤ K ≤ 37.

Выходные данные
Выходной файл OUTPUT.TXT должен содержать одно число – количество способов попадания в магазин.

Пример:

INPUT:
n = 2
k = 4

OUTPUT:

2

Моя попытка: я предположил, что здесь можно использовать числа Каталана. Но как окончательно оформить задачу - не знаю. Код работает для случая n=k, но в других случаях превышает результат на единицу.

#include <iostream>

using namespace std;


int catalan(int n, int k)
{
	int sum = 0;;

	if (n == k) // если число доступных шагов совпадает с числом шагов до магазина
	{
		sum = sum + 1;
		return sum;
	}

	if (k <= 1) // базовый случай для чисел Каталана
	{
		sum = sum+1;
		return sum;
	}

	if (abs(n-k) == 1 || n > k) 
	{
		sum = sum + 0;
		return sum;
	}
	else
	{
		for (int i=0; i<k; i++)
		{
			sum = sum + catalan(n, i) * catalan(n, n-i-1);
			
		}
		return sum;
	}
}

int main()
{
	int n = 2;
	int k = 4;

	int result = 0;

	result = catalan(n, k);

	cout << result;

	return 0;
}

[Serge_Bliznykov]

Сообщение от Константин01

Моя попытка: я предположил, что здесь можно использовать числа Каталана

простите, а как числа Каталана связаны с

Сообщение от Константин01

Задача динамического программирования

?

по моему, тут нужно взять массив размером n и заполнить сначала его.

теория по ДП - https://acm.susu.ru/materials/05_dynprog.pdf

[val_nnm]

Набросал решение на C# (на С++ переведите сами)

using System;
namespace ConsoleApp
{
    class Program
    {
        static int[] Data = new int[38];
        static int[] Data_tmp = new int[38];
        static void Main(string[] args)
        {
            int n = 2;
            int k = 4;

            Data[n] = 1;
            for (int i = 0; i < k; i++)
            {
                for (int j = 0; j < 38; j++)
                {
                    Data_tmp[j] = 0;
                    if (j > 1) Data_tmp[j] += Data[j - 1];
                    if (j < 36) Data_tmp[j] += Data[j + 1];
                }
                for (int j = 0; j < 38; j++)
                    Data[j] = Data_tmp[j];
            }
            Console.WriteLine(Data[0]);
            Console.ReadLine();
        }
    }
}