a bit of uva: UVa 10003 - Cutting Sticks

Problem Statement:
UVa 10003 - Cutting Sticks

Summary:
You are given a stick with length L, and N points where you need to cut the stick. Find the minimum total cost of cutting the sticks if the cost of each cutting operation is defined as the length of the stick before cutting.

Solution:
I like this problem because it can be solved with a very neatly written program! :P
Firstly notice that after each operation of cutting, we form two subproblems which are essentially the same as the original problem, hence the determination of the minimum cost can be done recursively. The recursion relationship is: let \(M(L,R)\) be the minimum cost needed to complete the necessary cuts from between point \(L\) and \(R\), then we have \(M(L,R) = min_{L < k < R}\{ \text{len}(L,R) + M(L, k) + M(k, R) \} \). Then we just need a memoization table to store all possible values of M(L,R), since the subproblems often overlap (and hence Dynamic Programming to the rescue!) and really there are at most \(O(N^2)\) subproblems.

Sample C++ implementation:

int a[55];
int N;
int dp[55][55];
//0 stores 0, N+1 stores full length
//1 indexed
int rec(int L, int R){
    if(L+1 == R) return 0;
    if(dp[L][R] != -1) return dp[L][R];
    int ans = MAXINT;
    for(int i=L+1;i<R;++i){
        ans = min(ans, a[R] - a[L] + rec(L, i) + rec(i, R));
    }
    dp[L][R] = ans;
    return ans;
}