Dynamic Programming Task

[TheDoCtoR]

Hi guys, I need your help about something in C++. So, very soon I'm going to have a competition in C++ programming in my school and we were just introduced to dynamic programming in our C++ class. However, I was a bit late and missed almost a half of lecture. I do understand what dynamic programming basically is, solving a bigger problem by solving smaller subproblems that have the same properties as the big problem... Now, the professor is very good and I somehow was able to understand the algorithm, but I have no idea how to implement it in C++ when trying to solve some exercises.
So, here's one task I'd like you to help me with. It's one of the easiest ones, but I'm sure that if I understand how to implement the algorithm here, I'll know how to solve bigger problems. The task text is in Croatian however, so I'm going to try and translate it.
"One day Marco searched through his grandfather's stuff and found a dusty map of buried golden treasures (the grandfather was a pirate). On the map there is a geographical web that splits the map on N rows and M columns. Marco's ship is in the upper left corner of the web (or map). He wanted to collect all the treasures, but his ship is partly wrecked and can move only right or down on the map. Marco wants us to write a program that is going to allow him to collect as many treasures as possible by moving ONLY up or down."

INPUT DATA:
- natural number N (1 <= N <= 1000) and M (1 <= M <= 1000) --> numbers of rows and columns on the map
- next N rows contain the content of the map, where '.' means no treasure and 'D' means there is a treasure on those coordinates

OUTPUT DATA:
- maximum number of treasures that can be collected by moving ONLY up or down

EXAMPLE OF TEST DATA:

Standard Input
4 5
. . D . .
. D . . .
D . . . .
. . D . D

Standard Output
3

Also, don't use any libraries except <iostream> or <cstdio> please. :) Thank you very much!!

[ne555]

> moving ONLY up or down
that would restring him to only one column, given that the initial position is fixed (upper left) then you only care for the first column and the rest is noise.

maybe it was `right' or `down'.
edit:
> but his ship is partly wrecked and can move only right or down on the map.
> collect as many treasures as possible by moving ONLY up or down.
¿which is it?


> but I have no idea how to implement it in C++
If the problem is the implementation, then provide pseudocode and I would translate it for you.

[keskiverto]

http://amrita.vlab.co.in/?sub=3&brch=274&sim=1431&cnt=1

However, that algorithm can move right, down, and diagonally, and has "gap penalty". Your pirate has a bit simpler life.

[Smac89]

Just thinking out loud:

- Speaking in terms of graph theory, from top down, each 'D' has a maximum of 2 neighbours (right or down)
- Can be solved using DFS or BFS(or IDDFS)

http://en.wikipedia.org/wiki/Depth-first_search
http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search

[TheDoCtoR]

I'm sorry about misunderstanding, the ship can move both right and down whenever it wants, but not diagonally.

[keskiverto]

score[i][j] = max( score[i-1][j], score[i][j-1] ) +
              ( map[i][j] has treasure ) ? 1 : 0;

00111
01111
11111
11223

It looks like there are 10 different routes that all return 3 caches.

[Smac89]

#include <iostream>
#define MAX(A, B) ((A ^ ((A ^ B) & -(A < B))))
using namespace std;

int main()
{
	int path[1000] = {0}, row, col;
	char ch;

	for (cin >> row >> col; row--; )
	{
		cin >> ch;
		path[0] += (ch == 'D' ? 1 : 0);
		for (int c = 1; c < col; ++c)
		{
			cin >> ch;
			path[c] = MAX(path[c], path[c - 1]) + (ch == 'D' ? 1 : 0);
		}
	}
	
	cout << path[col-1] << endl;
	return 0;
}

[TheDoCtoR]

Thank you so much for help everyone, today I asked my professor about the topic and he explained it to me very well. I managed to solve the task both iteratively and recursively using dynamic programming with memoization. :) Problem solved :D