помогите пожалуйста решить задачу на динамическое програмирование

Рейтинг: -4Ответов: 1Опубликовано: 24.03.2023

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

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

Входные данные

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

Выходные данные

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

Пишет "Программа использовала слишком много памяти и была прервана"

#include <iostream>
#include<vector>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    vector<vector<int>> v(a, vector<int>(b));
    vector<vector<int>> d(a, vector<int>(b));
    for (int i = 0; i < a; i++) {
        for (int j = 0; j < b; j++) {
            cin >> v[i][j];
        }
    }
    d[0][0] = v[0][0];
    for (int i = 1; i < a; i++) {
        d[0][i] = d[0][i - 1] + v[0][i];
    }
    for (int i = 1; i < b; i++) {
        d[i][0] = d[i - 1][0] + v[i][0];
    }
    for (int i = 1; i < a; i++) {
        for (int j = 1; j < b; j++) {
            d[i][j] = min(d[i - 1][j], d[i][j - 1]) + v[i][j];
        }
    }
    cout << d[a - 1][b - 1];
    return 0;
}

Ответы

▲ 0Принят

У вас перепутаны размерности, проследите, где нужно а, где b

for (int i = 1; i < b; i++) {
    d[0][i] = d[0][i - 1] + v[0][i];
}
for (int i = 1; i < a; i++) {
    d[i][0] = d[i - 1][0] + v[i][0];
}