
Так как речь идет о таблице, то лучше перебрать рекурсивно. Логично, что количество путей для клетки (i,j) - это количество путей для правой соседней клетки + количество путей для нижней соседней клетки.
При таком условии мы будем посещать те же клетки слишком часто, однако значение для них меняться не будет. Имеет смысл вычислить их единожды и запомнить для последующих использований. (На самом деле, достаточно иметь буфер вместимостью всего в 6 элементов, но мы сделаем полное запоминание).
(Иллюстрация 3 - таблица кэша)
Иллюстрации кода и возможного вывода прикреплены в дополнительных материалах.
========================
Ваши оценки и отзывы позволяют лучше оценить качество ответа.
Если ответ удовлетворил, не забудь отметить его как "Лучший".
Успехов в учёбе!
========================
Код:
cache = {}
def calculate_max_way_price(x: int, y: int, m:int, n:int):
if (x, y) in cache:
return cache[(x, y)]
x_way, y_way = 0, 0
if x < m - 1:
x_way = calculate_max_way_price(x + 1, y, m, n)
if y < n - 1:
y_way = calculate_max_way_price(x, y + 1, m, n)
if x == m - 1 and y == n - 1:
cache[(x, y)] = 1
return 1
cache[(x, y)] = x_way + y_way
return x_way + y_way
N = int(input())
M = int(input())
print(calculate_max_way_price(0, 0, N, M))

Так как язык не указан, написал пример на C++
К ответу прилагаются скриншоты кода и примера запуска.
Код:
#include <iostream>
#include <vector>
void complex_loop(int from, int to, int pointer, int depth,
std::vector<int> markers,
const std::function<void(std::vector<int>)>& do_something)
{
if (pointer < depth - 1)
for (markers[pointer] = from; markers[pointer] <= to; ++markers[pointer]){
complex_loop(from, to, pointer+1, depth, markers, do_something);
}
else
for (markers[pointer] = from; markers[pointer] <= to; ++markers[pointer]){
do_something(markers);
}
}
void complex_loop(int from, int to, int depth,
const std::function<void(std::vector<int>)>& do_something)
{
complex_loop(from, to, 0, depth, std::vector(depth, from), do_something);
}
template <typename T>
void print_sequence(std::vector<T> sequence) {
std::cout << "(" << sequence[0];
for(auto i = 1; i < sequence.size(); ++i){
std::cout << ";" << sequence[i];
}
std::cout << "); ";
}
int main() {
int n, k;
std::cin >> n >> k;
complex_loop(1, n, k, print_sequence<int>);
return 0;
}

