c - 不知道如何使用哈希表解决问题

Question

我必须使用哈希表解决以下问题（在 C 中）（我假设使用哈希表，因为我们现在正在研究哈希表）：

输入的第一行有 2 个数字：n，m

接下来，我们输入n行m个数字。（所以一个n*m矩阵）我们必须从左上角到右下角（只能通过向南或向东移动）。我们穿过的每个单元格要么将单元格中的数字添加到变量“ s ”中，要么减少它。因此，如果我们用 -5 遍历一个单元格，我们将得到s-5，如果我们用 +3 遍历一个单元格，我们将得到s+3。最开始，s是左上角的数字，总是>0。另一个规则是我们不能遍历数字为 0 的单元格。此外，每次离开单元格时都必须减 1，因此每次离开单元格时都会得到s-1。输出必须是最大值s到达右下角后即可获得。这是输入/输出的示例：

保证至少有一条到右下角的路径最终将给出至少等于 1的s ，因此如果最终s为负数，则该路径肯定是错误的。

我很难解决这个问题（尤其是使用哈希表），所以非常感谢任何帮助。另外，有没有其他更有效的解决方法？

标签： cdata-structureshashtable

Answer 1

这似乎是一个非常简单的动态规划问题。

设左上角为索引(0, 0)，右下角为该位置的数字。然后对于所有这样的和，定义为从一个位置到另一个位置的最大可能，如果这是不可能的。(n - 1, m - 1)arr[i][j](i, j)i, j0 <= i < n0 <= j < mf(i, j)s(0, 0)(i, j)-1

定义combine(previousS, valueInCell)为INT_MINifpreviousS = INT_MIN或valueInCell = 0，previousS + valueInCell - 1否则。

然后我们看到以下是真的：

f(0, 0) = arr[0, 0]
f(i, 0) = combine(f(i - 1, 0), arr[i][0])为所有人1 <= i < n
f(j, 0) = combine(f(j - 1, 0), arr[0][j])为所有人为1 <= j < m
f(i, j) = combine(max(f(i - 1, j), f(i, j - 1)), arr[i][j])所有人1 <= i < n1 <= j < m

特别是，我们正在寻找f(n - 1, m - 1).

现在这是一个递归算法，但是递归将非常低效，因为我们每次最多可以进行 2 次递归调用。因此，我们将定义一个数组f[i][j]来保存 的值f。

int combine(int previous_s, int value_in_cell) {
    return previous_s == INT_MIN || value_in_cell == 0 ? INT_MIN : previous_s + value_in_cell - 1;
}

int max(int i, int j) {
    return i > j ? i : j;
}

int computeS(int n, int m, int** arr) {
    int** const f = malloc(n * sizeof *f);
    int** const end_f = f + n;
    for(int** j = f; j < end_f; j++) {
        *j = malloc(m * sizeof **j);
    }
    f[0][0] = arr[0][0];
    for(int i = 1; i < n; i++) {
        f[i][0] = combine(f[i - 1][0], arr[i][0]);
    }
    for(int j = 1; j < m; j++) {
        f[0][j] = combine(f[0][j - 1], arr[0][j]);
    }
    for(int i = 1; i < n; i++) {
        for(int j = 1; j < m; j++) {
            f[i][j] = combine(max(f[i - 1][j], f[i][j - 1]), arr[i][j]);
        }
    }
    int const ret_val = f[n - 1][m - 1];
    for(int** j = f; j < end_f; j++) {
        free(*j);
    }
    free(f);
    return ret_val;
}

如您所见，不需要哈希表。

执行 I/O 的代码：

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    int** const arr = malloc(n * sizeof *arr);
    int** const end_arr = arr + n;
    for(int** j = arr; j < end_arr; j++) {
        *j = malloc(m * sizeof **j);
        for(int* k = *j; k < *j + m; k++) {
            scanf("%d", k);
        }
    }
    
    printf("%d\n", computeS(n, m, arr));
    
    for(int**j = arr; j < end_arr; j++) {
        free(*j);
    }
    free(arr);
    
    return 0;
}