#include <iostream>
#include <iomanip>
using namespace std;
int** matrCreate(int n)
{
int** M;
M = new int *[n];
for (int i = 0; i < n; i++)
M[i] = new int [n];
return M;
}
void matrInit(int** M, int n)
{
srand(time(0));
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
M[i][j] = rand()%199 - 99 ;
}
void matrPrint(int** M, int n)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
cout << setw(5) << M[i][j];
cout << endl;
}
}
void matrTransform(int** M, int n)
{
int im, jm, max = -1000, s = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if (M[i][j] > max)
{
max = M[i][j];
im = i;
jm = j;
}
if (i == j)
s += M[i][j];
}
}
M[im][jm] = s;
}
void clearMem(int** M, int n)
{
for (int i = 0; i < n; i++)
{
delete [] M[i];
}
delete [] M;
}
int main()
{
int n;
cin >> n;
int **A;
A = matrCreate(n);
matrInit(A, n);
matrPrint(A, n);
cout << endl;
matrTransform(A, n);
matrPrint(A, n);
clearMem;
return 0;
}
Так как речь идет о таблице, то лучше перебрать рекурсивно. Логично, что количество путей для клетки (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))
