EllysSocks.cpp

    vector<int> S;
    int dp[1005][1005];//minimum difference
    int inf = 0x3f3f3f3f;
    //careful the base case 
    int solve(int p, int n){
        if(p==0) return 0;
        if(n==1) return p==1 ? S[1]-S[0] : inf;
        if(n<1) return inf;
    
        int &ans = dp[p][n];
        if(ans!=-1) return ans;
        //         not use sock #n & use sock #n, #n-1
        return ans=min(solve(p, n-1), max(S[n]-S[n-1], solve(p-1, n-2)));
    }
    
    int getDifference(vector<int> s, int P) {
        S=s;
        memset(dp, -1, sizeof(dp));
        sort(S.begin(), S.end());
        return solve(P, S.size()-1);
    }
    
    //Bottom-up: do we need third loop?
    int getDifference(vector<int> S, int P) {
        sort(S.begin(), S.end());
        int dp[1005][1005], n=S.size(), ans=inf;
        memset(dp, -1, sizeof(dp));
        dp[0][0]=0;
        dp[1][1]=S[1]-S[0];
        for(int i=1;i<=P;++i){
            for(int j=0;j<n;++j){
                for(int k=j-2;k>=0;k--){//pick p-1 pair best
                    if(dp[i-1][k]>=0){
                        dp[i][j] = max(S[j]-S[j-1],dp[i-1][k]);
                    }
                }
                if(i==P && dp[i][j]!=-1) ans=min(ans, dp[i][j]);
            }
        }
        return ans;
    }

what's wrong in bottom-up approach?