Blog entries - Codeforces

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

so I was solving a standard dp problem but it got TLE using this form of the calc function

code

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.

code

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

Full text and comments »

i3mr125's blog