0

I'm having some trouble resolving a problem that I believe needs the use of depth-first-search algorithm.

This problems involves trying to find the biggest value of the path, but every time you walk through the path, you can either go straight or to your left.

Here is a example of a path:

 _
|2|_
|2|1|_
|4|9|4|_
|3|2|1|2|

The biggest value in this path would be 2+2+9+2 = 15

Now to the problem:

I've decided that the best way to solve this problem is to make a adjacency list and use a stack with DFS to get the biggest value of the path, but I'm having a hard time figuring out how to create the adjacency list, considering that the program input is:

4 //Number of lines
2 // First line
2 1 
4 9 4 
3 2 1 2

Here is what I have so far

// Recieve the size of the path
scanf("%d", &nN);

// Get the amount of elements in the list: n!
for( i = 0, nFact = 0 ; i < nN ; i++ )
    nFact += nN - i;

// Create list of adjacency
list = malloc( nFat * sizeof( List ) );

// Insert elements
for( i = 0 ; i < nN ; i++ ) {
    scanf("%d", list[i].value);
    lista[i].color = 0;
    lista[i].prox = NULL;
    // No idea on how to insert the elements on their specific slot and on their adjacency, as the number keeps increasing for each line
}
Dom
  • 39
  • 2
  • An adjacency list seems like a lot more trouble than it is worth if you can rely on there being no gaps, other than possibly at the bottom. Just store the scores in sequential elements of an array (up to `(nN * (nN + 1)) / 2` elements are needed). From the element at index `x`, the choices of next step are the ones at index `2 * x + 1` and `2 * x + 2`. – John Bollinger May 27 '15 at 13:00
  • Note, too, that although you certainly can use an explicit stack data structure, and you even know up front what capacity it requires, you can also write the algorithm recursively. That gives you the call stack as your stack. – John Bollinger May 27 '15 at 13:05
  • I don't believe `2 * x + 1` and `2 * x + 2` would be enough to get the next step of them, for example: `2,2,1,4,9,4,3,2,1,2`, if you get the second 4 it should point to 1 and 2, but if you use the formula it won't point to anyone. – Dom May 27 '15 at 13:14
  • Hmm, my bad. Those formulae are for a binary tree, which is not actually what you have. Nevertheless, there should be an arithmetic approach. Perhaps I can work it out. – John Bollinger May 27 '15 at 13:23
  • Ok, it's not bad. You just need to keep track of which step you're on. On the first step, the choices are `x + 1` and `x + 2`. On the second, they are `x + 2` and `x + 3`. On the `n`th they are `x + n` and `x + n + 1`. – John Bollinger May 27 '15 at 13:30
  • I've managed to make the program work, but I had to use recursion to make it able to get the biggest value, would there be any other faster way? As the online judge gives me a timeout limit in one case. – Dom May 28 '15 at 02:31

1 Answers1

0

At first, I want to ask you a question: Why using list? Can we use array instead of list?

For example, Assume that we are in array[i][j]:

  • if we want to move right, then we are in array[i][j+1]
  • if we want to move down, we are in array[i+1][j]

So I think we should just use Array to present our datastructures.

You picked up that DFS can solve your problems, so we have a look at what we should do:

int dfs(int **array, int row, int column) {
    if (row == m || column == n) return 0;
    int res = array[row][column];
    int option_right = dfs(array, row, column + 1);
    int option_down = dfs(array, row + 1, column);
    return std::max(option_right, option_down) + res;
}

It can solve this problem, but we should notice that the big(O) is very large: O(exponential)， we must make some improvement:

Dynamic Programming

What is the difference between memoization and dynamic programming?

Community
  • 1
  • 1
kaitian521
  • 548
  • 2
  • 10
  • 25
  • You've mistaken the options for the path: from the example, they are (1) straight down, and (2) down + right (the OP's use of "left" seems to be from the point of view of a person actually walking forward along the path). You're quite correct that a DP approach scales much better, though. It would be pretty easy to write one, too, as you just need to work from the bottom up instead of from the top down. – John Bollinger May 27 '15 at 13:39
  • The biggest problem using this code is that I still get timeout limit in one of the cases, even when I have another way of telling me that I have already passed through that path, returning me the its biggest value, instead of running through it again. – Dom May 28 '15 at 02:35
  • By using DP, you can reduce the time complexity to O(m*n), but my answer is something wrong according to John – kaitian521 May 28 '15 at 06:17