Uva 10003 Solution

#include<bits/stdc++.h>
using namespace std;
vector<int>cut(55);
int r[55][55];
int minimum_cost(int a, int b)
{
    if(b-a == 1)
        return 0;

    if(r[a][b] != -1)
        return r[a][b];

    int mini = 1000000;

    for(int i=a+1;i<b;i++)
    {
        mini = min(((cut[b]-cut[a]) + minimum_cost(a, i) + minimum_cost(i, b)), mini);
    }

    r[a][b] = mini;

    return mini;
}
int main()
{
    int l, n, i, j;
    while(cin >> l && l != 0)
    {
        cin >> n;

        cut.clear();
        cut[0] = 0;

        for(i=1;i<=n;i++)
            cin >> cut[i];

        cut[n+1] = l;

        for(i=0;i<55;i++)
        {
            for(j=0;j<55;j++)
            {
                r[i][j] = -1;
            }
        }

        int result = minimum_cost(0, n+1);

        cout << "The minimum cutting is " << result << ".\n";
    }

    return 0;
}