不知道如何使用哈希 table 来解决问题

Question

我必须使用散列 table 解决以下问题（在 C 中）（我假设使用散列 table 因为我们现在正在研究散列 tables）：

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

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

保证至少有一条路径到右下角，最后s至少等于1，所以如果最后s为负路径保证是错误的。

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

Answer 1

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

左上角的索引为(0, 0)，右下角的索引为(n - 1, m - 1)，arr[i][j]为(i, j)位置的数字。然后对于所有 i, j 使得 0 <= i < n 和 0 <= j < m，将 f(i, j) 定义为从位置 (0, 0) 到位置 [= 的最大可能 s =15=]，如果不可能，则 -1。

定义 combine(previousS, valueInCell) 为 INT_MIN 如果 previousS = 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 < n 和 1 <= 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;
}

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

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

Answer 2

正如 Mark 提到的，这是动态规划问题。所以这个问题与hashtable无关。现在，由于 Mark 的回答有点难以理解，我将尝试解释我的解决方案。给定的问题类似于标准矩阵路径优化问题，但有两个有趣的转折。

解法路径不能包含0 valued cells.
以上也是一道标准题。但这是转折点。由于单元格具有整数值。由于先前的加法和减法运算，将很难区分原始 0 valued cells 和中间 dp 矩阵中的矩阵。

所以为了解决上述问题，我们需要单独存储原始0 valued cells的索引。最简单的方法是创建另一个参考矩阵并标记 0 valued cells.

现在，我们应用简单的动态规划技术。

dp[i][j]= dp[i][j] + max(dp[i-1][j],dp[i][j-1]) - 1;
if (zeroed[i][j] == 1) 即 0 valued cell 然后忽略此单元格。
if (zeroed[i-1][j] == 1) 然后忽略顶部单元格的添加。
if (zeroed[i][j-1] == 1) 然后忽略左侧单元格的加法。
dp[row-1][col-1]为优化答案。

这就是我们解决这个问题的方法。如果你还是觉得难，那你就需要学习动态规划了。程序代码：

#include<iostream>
using namespace std;
int zeroed[50][50]; //for reference of 0 valued cells
int main(){
        int dp[50][50];
        int row,col,value;
        cin>>row>>col;
        /*=========initializing matrix========*/
        for(int i=0;i<row;i++){
                for(int j=0;j<col;j++){

                        cin>>value;
                        dp[i][j]=value;
                        if(value == 0){
                                zeroed[i][j]=1; //marking 0 valued cell
                        }

                }
        }

        /*==========applying dynamic programming=====*/
        for(int i=0;i<row;i++){
                for(int j=0;j<col;j++){
                        if(zeroed[i][j]== 1){
                                continue; //just ignore this cells
                        }
                        if(i>0 && j>0){
                                if(zeroed[i-1][j] !=1 && zeroed[i][j-1]!=1){
                                        dp[i][j]+=max(dp[i-1][j],dp[i][j-1]) - 1;
                                }else if(zeroed[i-1][j]!=1){
                                        dp[i][j]+= dp[i-1][j] - 1;
                                }else if(zeroed[i][j-1]!=1){
                                        dp[i][j]+=dp[i][j-1] - 1;
                                }
                                //ignore other cases

                        }else if(i>0){
                                if(zeroed[i-1][j]!=1){
                                        dp[i][j]+=dp[i-1][j] - 1;
                                }
                                //ignore other cases
                        }else if(j>0){
                                if(zeroed[i][j-1]!=1){

                                        dp[i][j]+=dp[i][j-1] - 1;
                                }
                                //ignore other cases
                        }
                }
        }
        cout<<dp[row-1][col-1];//max s 
        return 0;
}

不知道如何使用哈希 table 来解决问题

Don't know how to use a hash table to solve a problem

c

data-structures

hashtable