CUBE-104: Tasty Chocolate

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

const int INF = 1e9;
int ar[1001];
int n, MX = 0;
vector <vector<int>> dp(1001, vector<int> (3001,INF));

int f(int i, int mx){

    if(i == n) {
        if(ar[i] <= mx)
            return dp[i][mx] = 1;
        return dp[i][mx] = 0;
    }

    if(dp[i][mx] != INF) return dp[i][mx];

    for(int j = mx+1; j <= MX; j++){
        int x = f(i+1, j);
        if(j == ar[i]) dp[i][mx] = min(dp[i][mx], x);
        else dp[i][mx] = min(dp[i][mx], x + 1);
    }

    return dp[i][mx];
}

int main(){

    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&ar[i]);
        MX = max(MX, ar[i]);
    }

    printf("%d", f(1,0));

    return 0;
}