so I was solving a standard dp problem but it got TLE using this form of the calc function
code
and it passed by defining the same function exactly outside the solve function like this.
code
So I really don't understand the issue here
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
so I was solving a standard dp problem but it got TLE using this form of the calc function
void solve(){
string a,b;
cin >> a >> b;
vector<vector<int>>dp(N,vector<int>(N,-1));
int n = sz(a), m = sz(b);
function<int(int,int)>calc=[&](int i,int j)->int{
if(i==n&&j==m)
return 0;
if(i>n||j>m)
return INT_MAX;
if(~dp[i][j])
return dp[i][j];
int op1 = calc(i,j+1)+1;
int op2 = calc(i+1,j)+1;
int op3 = calc(i+1,j+1)+(a[i]!=b[j]);
return dp[i][j] = min({op1,op2,op3});
};
cout << calc(0,0);
}
and it passed by defining the same function exactly outside the solve function like this.
vector<vector<int>>dp(N,vector<int>(N,-1));
int n,m;
string a,b;
int calc(int i,int j){
if(i==n&&j==m)
return 0;
if(i>n||j>m)
return INT_MAX;
if(~dp[i][j])
return dp[i][j];
int op1 = calc(i,j+1)+1;
int op2 = calc(i+1,j)+1;
int op3 = calc(i+1,j+1)+(a[i]!=b[j]);
return dp[i][j] = min({op1,op2,op3});
}
void solve() {
cin >> a >> b;
n = sz(a), m = sz(b);
cout << calc(0,0);
}
So I really don't understand the issue here
Name |
---|