Dynamic Programming -- UVa 10003

UVa 10003: Cutting Sticks

Recursive + Memoization = Top-Down Dynamic Programming

Accepted Code:

int Cut(int left, int right)
{
    if (!visited[left][right])
    {
        int cost = 1 << 30;
        for (int i = left + 1; i < right; i++)
        {
            cost = minimum(cost, 
                Cut(left, i) + Cut(i, right) + (coord[right] - coord[left]));
        }
        memoization_cut[left][right] = cost;
        visited[left][right] = true;
    }
    return memoization_cut[left][right];
}