UVa - 10003 - Cutting Sticks

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

vector <int> cut;
int dp[53][53];

int cutting_sticks(int x, int y){
    int sum, mn;
    if(x+1 == y)return 0;
    if(dp[x][y] != -1)return dp[x][y];
    mn = 111111111;
    for(int i = x+1; i < y; i++){
        sum = cutting_sticks(x, i) + cutting_sticks(i, y) + (cut[y]-cut[x]);
        mn = min(mn, sum);
    }
    dp[x][y] = mn;
    return dp[x][y];
}

int main(){
    int stick, piece, length;
    while(cin >> stick){
        if(!stick)break;
        cut.clear();
        memset(dp, -1, sizeof(dp));
        cut.push_back(0);
        cin >> piece;
        for(int i = 1; i <= piece; i++)cin >> length, cut.push_back(length);
        cut.push_back(stick);
        int sz = cut.size()-1;
        int ans = cutting_sticks(0, sz);
        cout << "The minimum cutting is " << ans << "." << endl;
    }
    return 0;
}