Количество путей с использованием k монет ⇐ C++

[Anonymous]

Дана матрица, в каждой ячейке которой находится некоторое количество монет. Посчитайте количество способов добраться до нижнего правого угла из верхнего левого, используя ровно k монет. Мы можем перейти к (i+1, j) и (i, j+1) из ячейки (i, j).

Пример:

Ввод: k = 12

Код: Выделить всё

   mat[][] = { {1, 2, 3},
{4, 6, 5},
{3, 2, 1}
};

Выход:
2 Есть два пути с 12 монетами

1 -> 2 -> 6 -> 2 -> 1

1 -> 2 -> 3 -> 5 -> 1


Для этого я создал рекурсивное определение:


Пусть Count(i, j, k) — количество способов добраться из M[0][0] в M[ j] с использованием k монет.

Код: Выделить всё

Count(i, j, k) = {
0:                                       if M[i][j] > k,
Count(i-1, j, k-1) + Count(i, j-1, k-1): if M[i][j] < k
}

Я аргументирую это определение тем, что запись в матрице (количество монет) больше, чем количество монет, которое мы хотим (

Код: Выделить всё

k

), то мы не можем пойти по этому пути, поэтому значение в таблице должно быть 0.

Если запись меньше или равна значению количество монет, то мы можем выбрать этот путь, сложив количество путей сверху (i-1,j) и слева (i, j-1). Я вычитаю k на 1, потому что количество монет из последней записи было на 1 меньше.

Вот как я это делаю в следующей функции динамического программирования:

Код: Выделить всё

#include 
#include 
#include 
using namespace std;

#define MAX_SIZE  10
#define MAX_COINS 20

int Count[MAX_SIZE][MAX_SIZE][MAX_COINS]; // number of ways to get from M[0][0] to M[i][j] using k coins
std::vector M;

int NumOfPaths(int C) {
size_t N = M.size();
// Number of paths to (0,0) with 1 coin is 1
Count[0][0][1] = 1;
// zero coins doesn't work
for (size_t i = 0; i < N; ++i) for (size_t j = 0; j < N; ++j)
Count[i][j][0] = 0;

// If the number of coins is greater than the max then Count[i][j][k] = 0;
// Otherwise Count[i][j][k] = Count[i-1][j][k-1]+Count[i][j-1][k-1]

for (size_t i = 1; i 

Подробнее здесь: [url]https://stackoverflow.com/questions/37311139/number-of-paths-using-k-coins[/url]