ДАЮ 70 БАЛЛОВ
Робот-кладоискатель находится в левом нижнем углу лабиринта. В каждой клетке записано, сколько золотых монет там лежит. Робот может двигаться только вправо или вверх (на одну клетку), и ему нужно добраться до правого верхнего угла лабиринта. Какое наибольшее количество золотых монет он сможет собрать по дороге к выходу? Если робот оказывается в клетке, то он забирает все монеты из этой клетки.
Answers & Comments
Ответ 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];
}