Помогите пожалуйста. Динамическое программирование

Question

Помогите пожалуйста. Динамическое программирование

фрол зайдель Ученик (48), закрыт 1 неделю назад

Исполнитель Сладкоежка живет в квадрате 5 на 5 клеток. Он может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо – Сладкоежка перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю клетку. При попытке выйти за границу квадрата Сладкоежка разрушается. В каждой клетке квадрата лежат конфеты, в количестве от 1 до 10 штук. Посетив клетку, исполнитель забирает себе конфеты. Определите максимальное количество конфет, которое может собрать Сладкоежка, перемещаясь из левой верхней в правую нижнюю клетку квадрата.В ответ запишите только число.

Answer 1

 #include  
using namespace std;
#define max(a,b) (a)>(b)?(a):(b) 
 
int main() 
{ 
	const int n = 5; 
	int arr[n][n] = { 
		{1,1,5,1,3}, 
		{1,2,4,1,2}, 
		{2,3,3,1,3}, 
		{3,4,2,1,1}, 
		{2,5,1,1,2} 
	}; 
	for (int i = 1; i < n; i++) arr[0][i] += arr[0][i - 1]; 
	for (int i = 1; i < n; i++) arr[i][0] += arr[i - 1][0]; 
	for (int i = 1; i < n; i++) for (int j = 1; j < n; j++) arr[i][j] += max(arr[i - 1][j], arr[i][j - 1]); 
	cout << "Sugareater can to eat about " << arr[n - 1][n - 1] << " pounds of sheet."; 
}

21

Answer 2

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