basic observation leads to dp OPTIMIZATION from O(n^3) to O(n^2) !!! (sopj : AMBLE), C++ (gcc)

basic observation leads to dp OPTIMIZATION from O(n^3) to O(n^2) !!! (sopj : AMBLE)

#include <bits/stdc++.h>
     
    using namespace std;
    typedef long double ld;
    typedef long long int ll;
    #define pii pair<ll, ll>
    #define mp make_pair
    #define pb push_back
     
    inline ld dis(const pii& p1, const pii& p2){
        ld ans = (p1.first - p2.first)*(p1.first - p2.first) + (p1.second - p2.second)*(p1.second - p2.second);
        return sqrt(ans);
    }
     
    ld dp[1001][1001];
     
    int n;
     
    vector<pii> p;
     
    /*ld foo(int pos, int lst){
        if(pos == n-1) return (dis(p[lst], p[n-1]));
        ld &ans = dp[pos][lst];
        if(ans == 0){
            ans = (ll)1e18;
            ld pre = 0;
            for(int j = pos+1; j < n; j++){
                ld cur = dis(p[pos], p[j]) + pre + foo(j, lst);
                ans = min(ans, cur);
                pre += dis(p[lst], p[j]);
                lst = j;
            }
        }
        return ans;
    }*/
     
    //significant improvement in runtime by using an observation! i.e. pos = max(pos1, pos2).
     
    ld foo(int pos1, int pos2){
        int pos = max(pos1, pos2) + 1;
        if(pos == n-1) return (dis(p[pos1], p[n-1]) + dis(p[pos2], p[n-1]));
        ld &ans = dp[pos1][pos2];
        if(ans == 0){
            ans = min((dis(p[pos1], p[pos]) + foo(pos, pos2)), (dis(p[pos2], p[pos]) + foo(pos1, pos)));
        }
        return ans;
    }
     
    int main(){
        memset(dp, 0, sizeof(dp));
        cout << fixed << setprecision(2);
        scanf("%d",&n);
        for(int j = 0; j < n; j++){
            int x, y;
            scanf("%d %d",&x ,&y);
            p.pb(mp(x, y));
        }
        sort(p.begin(), p.end());
        if(n == 1){
            cout << 0;
            return 0;
        }
        else if(n == 2){
            cout << (dis(p[1], p[0])*2) << endl;
            return 0;
        }
        cout << foo(0, 0) << endl;
        return 0;
    }


run \| edit \| history \| help	0