UVA-10003: Cutting Sticks

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int l,n;
int ar[51];
int dp[1001][1001];
int f(int i,int j){
    if(dp[i][j]!=INF) return dp[i][j];
    bool have=false;
    for(int k=1;k<=n;k++){
        if(ar[k]>=i && ar[k]<j){
            dp[i][j]=min(dp[i][j], f(i,ar[k])+f(ar[k]+1,j)+(j-i+1) );
            have=true;
        }
    }
    if(have){
        return dp[i][j];
    }
    else {
        return 0;
    }

}
int main(){
    scanf("%d%d",&l,&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&ar[i]);
    }
    for(int i=1;i<=l;i++){
        for(int j=1;j<=l;j++){
            dp[i][j]=INF;
        }
    }
    cout<<f(1,l);
    return 0;
}