c - 使用深度优先搜索找到具有最大值(value)的路径

Question

我在解决一个我认为需要使用深度优先搜索算法的问题时遇到了一些麻烦。

这个问题涉及到试图找到路径的最大值，但是每次你走过这条路径时，你要么直走，要么向左走。

以下是路径示例:

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

该路径中的最大值为 2+2+9+2 = 15

现在解决问题:

我决定解决这个问题的最好方法是创建一个邻接表并使用带有 DFS 的堆栈来获取路径的最大值，但我很难弄清楚如何创建邻接表，考虑程序输入为:

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

这是我到目前为止所拥有的

// 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
}

Answer 1

首先我想问大家一个问题: 为什么使用列表？我们可以使用数组代替列表吗？

例如，假设我们在array[i][j]中:

• 如果我们想向右移动，那么我们就在array[i][j+1]
• 如果我们想向下移动，我们在array[i+1][j]

所以我认为我们应该使用数组来呈现我们的数据结构。

您发现 DFS 可以解决您的问题，所以我们看看应该做什么:

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;
}

它可以解决这个问题，但是我们应该注意到big(O)非常大: O(指数)，我们必须做出一些改进:

动态规划

What is the difference between memoization and dynamic programming?