монетки на шахматной доске!

[grimm_jow]

Вот собственно задача:

Дана доска N*M, в каждой из её клеток лежит некое кол-во золотых монет.
Начинает игрок в левом нижнем углу доски. Нужно достичь верхнего правого угла, собрав максимум монет. Движение только вверх и вправо.

Пример входных данных:
0 8 4 0
5 1 2 2
0 3 1 9

Пример вывода программы:
18 ururr
(что означает 18 монет и путь up-right-up-right-right).


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

Вот тут кое-какие наброски.... правильно нет ??

#include <QtCore/QCoreApplication>
#include <QtCore/qDebug>
#define N 3
#define M 4

int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);

int mx[N][M];
//Generate marix
qDebug()<<"Matrix generate";
qDebug()<<"\n";
for (int i=0;i<N;i++)

{
for (int j=0;j<M;j++)
{

mx[i][j]=rand()%10;
printf("%3d",mx[i][j]);

}
qDebug()<<"\n";
}

qDebug()<<"\n";
qDebug()<<"Sobiraem monetki";
qDebug()<<"\n";

int start;
int up;
int right;

start=mx[2][0];

for (int i=0;i<N;i++)
{
for (int j=0;j<M;j++)
{
up=mx[N-2+i][j];
right=mx[j][M-2+j];
if (start+up>start+right)
{
start+up;
qDebug()<<start+up;

}
else
{
start+right;
qDebug()<<start+right;
}

}
}


return a.exec();
}

[Carbon]

Гугли "динамическое программирование".

[Serge_Bliznykov]

на форуме:
сюда сходите:
http://www.programmersforum.ru/showthread.php?t=82696

а потом по ссылкам в этой теме из пост #9

p.s. там разбирается алгоритм решения подобных задач