Question

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

Answer 1

Ответ 32.

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

#include <bits/stdc++.h>

 

using namespace std;

 

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

 

int main(){

   cin >> n >> m;

   for(int i = 1;i <= n;i++)

       for(int j = 1;j <= m;j++)

           cin >> a[i][j];

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

   for(int i = 1;i <= n;i++){

       for(int j = 1;j <= m;j++){

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

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

       }

   }

   cout << dp[n][m];

}