Help with "Jump on Buildings"

general
, ,
1

Problem: AMJMP Problem - CodeChef

In short, can anyone please share their approach for this problem? I think my code gives the right answers but is slow (since it gives a TLE).

MY CODE 
#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;

const int MAXN = 5e3+5;

int n;
vector<int> h(MAXN);
vector<int> jumps(MAXN);

int dp[MAXN][MAXN][2];

//dp[i][j][k]->dp[previous index][current index][direction]
int count(int i, int j, int k) {
    if(abs(i-j) == 1) return dp[i][j][k] = 0;
    if(dp[i][j][k] != -1) return dp[i][j][k];
    
    dp[i][j][k] = 0;
    if(k) {
        for(int next=j-1; next>i; next--) {
            if(h[next] < h[j])
                dp[i][j][k] = max(dp[i][j][k], 1+count(j,next,!k));
        }
    }
    else {
        for(int next=j+1; next<i; next++) {
            if(h[next] < h[j])
                dp[i][j][k] = max(dp[i][j][k], 1+count(j,next,!k));
        }
    }
    return dp[i][j][k];
}

int main() {
    FASTIO
    
    cin >> n;
    for(int i=0; i<n; i++) cin >> h[i];
    
    memset(dp,-1,sizeof(dp));
    
    int maxJumps = 0;
    for(int j=1; j<n; j++) {
        if(h[j] < h[0])
            maxJumps = max(maxJumps, 1+count(0,j,1));
    }
    jumps[0] = maxJumps;
    maxJumps = 0;
    for(int j=n-2; j>=0; j--) {
        if(h[j] < h[n-1])
            maxJumps = max(maxJumps, 1+count(n-1,j,0));
    }
    jumps[n-1] = maxJumps;
    
    for(int i=1; i<n-1; i++) {
        maxJumps = 0;
        for(int j=0; j<i; j++) {
            if(h[j] < h[i])
                maxJumps = max(maxJumps, 1+count(i,j,0));
        }
        for(int j=i+1; j<n; j++) {
            if(h[j] < h[i])
                maxJumps = max(maxJumps, 1+count(i,j,1));
        }
        jumps[i] = maxJumps;
    }
    
    for(int i=0; i<n; i++) cout << jumps[i] << " ";
    cout << "\n";
    
    return 0;
}