不知道如何使用哈希 table 来解决问题
Don't know how to use a hash table to solve a problem
我必须使用散列 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),所以非常感谢您的帮助。另外,有没有其他更有效的解决方法?
这似乎是一个非常简单的动态规划问题。
左上角的索引为(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;
}
正如 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 解决以下问题(在 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),所以非常感谢您的帮助。另外,有没有其他更有效的解决方法?
这似乎是一个非常简单的动态规划问题。
左上角的索引为(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;
}
正如 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;
}