ДАЮ 70 БАЛЛОВ Робот-кладоискатель находится в левом нижнем углу лабиринта. В каждой...

ДАЮ 70 БАЛЛОВ
Робот-кладоискатель находится в левом нижнем углу лабиринта. В каждой клетке записано, сколько золотых монет там лежит. Робот может двигаться только вправо или вверх (на одну клетку), и ему нужно добраться до правого верхнего угла лабиринта. Какое наибольшее количество золотых монет он сможет собрать по дороге к выходу? Если робот оказывается в клетке, то он забирает все монеты из этой клетки.

Ответ 32.

Вот алгоритм на с++

#include

using namespace std;

int n,a[1004][1004],dp[1004][1004],m;

int main(){

cin >> n >> m;

for(int i = 1;i

for(int j = 1;j

cin >> a[i][j];

dp[1][1] = a[1][1];

for(int i = 1;i

for(int j = 1;j

if(i == 1 && j == 1) continue;

dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]) + a[i][j];

}

cout

}