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

Question

我必须使用哈希表解决以下问题(用C语言)(假设使用哈希表，因为我们现在正在研究哈希表)：

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

接下来，我们输入带有m数的n行。(因此，一个n*m矩阵)我们必须从左上角到右下角(只能通过向南或向东移动)。我们交叉的每个单元要么将单元格中的数字添加到变量"s“中，要么将其缩小。因此，如果我们用-5遍历一个单元格，我们将有s-5，如果我们用+3遍历一个单元格，我们将得到s+3。在开头，的是左上角的数字，总是>0。另一条规则是，我们不能用数字0遍历单元格。而且，每次我们离开一个单元格时，我们必须减去1，所以每次我们离开一个单元格时，我们都会得到s-1。输出必须是到达右下角后可以获得的最大的。以下是输入/输出的示例：

​

​

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

我很难解决这个问题(尤其是使用哈希表)，所以任何帮助都是非常感谢的。还有其他更有效的方法来解决这个问题吗？

Answer 1

正如Mark提到的，这是动态规划问题。所以这个问题与哈希表无关。现在，由于Mark的回答不太容易理解，我将尝试解释我的解决方案。给出的问题类似于标准矩阵路径优化问题，有两个有趣的曲折。

解决方案路径不能包含0 valued cells.

• Above点也是一个标准问题。但这是个转折。因为单元格有整数值。由于以前的加法和减法运算，很难区分原始0 valued cells和中间dp矩阵中的那些。

因此，为了解决上述问题，需要分别存储原始0 valued cells的索引。最简单的方法是创建另一个引用矩阵并标记0 valued cells。

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

1. dp[i][j]= dp[i][j] + max(dp[i-1][j],dp[i][j-1]) - 1;
2. if (zeroed[i][j] == 1)是一个0 valued cell，然后忽略这个cell.
3. if (zeroed[i-1][j] == 1)，然后用顶部cell.
4. if (zeroed[i][j-1] == 1)忽略加法，然后用左cell.
5. 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;
}

Answer 2

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

让左上角给出指数(0, 0)和右下角的(n - 1, m - 1)，arr[i][j]是(i, j)位置中的数字。然后，对于所有的i, j，比如0 <= i < n和0 <= j < m，将f(i, j)定义为从(0, 0)位置到(i, j)位置的最大可能的s，如果这不可能的话，定义为-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]) for all 1 <= i < n

f(j, 0) = combine(f(j - 1, 0), arr[0][j]) for all 1 <= j < m

f(i, j) = combine(max(f(i - 1, j), f(i, j - 1)), arr[i][j]) for all 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;
}

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

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