Помогите пожалуйста с задачей на С++

Question

Помогите пожалуйста с задачей на С++

daniil@pigment-vtp.ru Эксперт пока не указал должность 1 месяц назад

В каждой клетке прямоугольной таблицы
? * M
N×M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).

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

Формат ввода
Вводятся два числа N и M — размеры таблицы (
1
≤
?
≤
20
1≤N≤20,
1
≤
?
≤
20
1≤M≤20). Затем идет N строк по M чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).

Формат вывода
Выведите минимальный вес еды в килограммах, отдав которую можно попасть в правый нижний угол.

5 5
1 1 1 1 1
3 100 100 100 100
1 1 1 1 1
2 2 2 2 1
1 1 1 1 1

вывод 11

Answer 1

Эта задача решается с помощью динамического программирования. Основная идея заключается в том, чтобы найти минимальную сумму штрафов, двигаясь по таблице только вправо или вниз.

### Шаги:
1. Используем двумерный массив `dp`, где каждая ячейка `dp[i][j]` будет хранить минимальный вес еды, необходимый для достижения клетки (i, j) из верхнего левого угла.
2. Начальная точка — это клетка (0, 0), вес которой равен штрафу в этой клетке.
3. Для остальных клеток:
- Если мы идем вправо, то берем минимальный путь из предыдущей клетки слева.
- Если идем вниз, то берем минимальный путь из предыдущей клетки сверху.
- Выбираем минимальное из этих двух значений и добавляем штраф за текущую клетку.

### Алгоритм:
1. Инициализируем массив `dp` размерами `N x M`, где `dp[0][0]` равен штрафу первой клетки.
2. Для каждой клетки (i, j) находим минимальный путь, основываясь на соседних клетках сверху и слева.
3. В конце, в правом нижнем углу (`dp[N-1][M-1]`), будет храниться минимальная сумма штрафов.

Вот пример кода на C++:

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
int N, M;
cin >> N >> M;

// Чтение таблицы штрафов
vector<vector<int>> grid(N, vector<int>(M));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cin >> grid[i][j];
}
}

// Массив для хранения минимального веса еды для каждой клетки
vector<vector<int>> dp(N, vector<int>(M));

// Инициализация первой клетки
dp[0][0] = grid[0][0];

// Заполнение первой строки (можно двигаться только вправо)
for (int j = 1; j < M; ++j) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}

// Заполнение первого столбца (можно двигаться только вниз)
for (int i = 1; i < N; ++i) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}

// Заполнение остальной части таблицы
for (int i = 1; i < N; ++i) {
for (int j = 1; j < M; ++j) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}

// Минимальный вес еды в правом нижнем углу
cout << dp[N - 1][M - 1] << endl;

return 0;
}
```

### Пояснение:
1. Мы считываем размеры таблицы `N` и `M`, а затем вводим таблицу штрафов `grid`.
2. Массив `dp` заполняется так:
- Ячейка `dp[0][0]` инициализируется значением первой клетки.
- Затем для первой строки и первого столбца заполняются значения на основе того, что можно двигаться только вправо или вниз соответственно.
- Для остальных клеток берется минимум между значениями сверху и слева, чтобы найти минимальный путь.
3. Выводится результат, который находится в правом нижнем углу таблицы `dp[N-1][M-1]`.

### Пример:
Вход:
```
5 5
1 1 1 1 1
3 100 100 100 100
1 1 1 1 1
2 2 2 2 1
1 1 1 1 1
```

Выход:
```
11
```

Это решение работает за \(O(N \times M)\), что является оптимальным для данной задачи.

Answer 2

 #include 
#include //лень писать функцию min как макрос 
#include 
using namespace std; 
int main() 
{ 
	size_t SizeN, SizeM; //размеры массива 
	cin >> SizeN >> SizeM; 
	size_t N = SizeM, Nmin1 = 0ULL; //начала строк (чтобы не перемножать в цикле) 
	vector MatrixNM(SizeN*SizeM); //одномерный массив [строка][столбец] => [строка*кол-во столбцов + столбец] 
	for (auto& i : MatrixNM) cin >> i; 
	for (size_t i = 1; i < SizeM; i++) MatrixNM[i] += MatrixNM[i - 1]; //Вычисление 0 строки 
	for (size_t i = 1; i < SizeN; i++) //Вычисление от 1 до последней строки 
	{ 
		MatrixNM[N] += MatrixNM[Nmin1]; //Вычисление нулевого столбца в i-й строке 
		for (size_t j = 1; j < SizeM; j++) //Вычисление столбцов > 0 в i-й строке 
		{ 
			MatrixNM[N + j] += min(MatrixNM[Nmin1 + j], MatrixNM[N + j - 1]); 
		} 
		N += SizeM; Nmin1 += SizeM; //вычисление начала i-й и (i-1)-й строки 
	} 
	cout << MatrixNM.back(); //Вывод последнего элемента как результата. 
}