length =  1  2  3  4  5  6  7  8
 price =  1  5  8  9 10 17 18 20

got a length of 8, want to cut it up to get maximum value out of it.
many possibilities

value(L) = total value we can get by cutting a length of L

value(8) = price[1] + value(7)   // OR means take the maximum
        OR price[2] + value(6)
        OR price[3] + value(5)
        OR price[4] + value(4)
        OR price[5] + value(3)
        OR price[6] + value(2)
        OR price[7] + value(1)
        OR price[8] + value(0)

value(0) = 0

value(1) = price[1]

value(2) = price[2]
        OR price[1] + value(1)

value(3) = price[3]
        OR price[2] + value(1)
        OR price[1] + value(2)

int value(int L)
{ if (L == 0)
    return 0;
  int max = 0;
  for firstcut = 1 to L
    cut_here_value = price[firstcut] + value(L-firstcut);
    if (cut_here_value > max)
      max = cut_here_value
  return max; }

int value[totallength]

value[0] = 0;
for L = 1 to totallength
  int max = 0;
  for firstcut = 1 to L
    cut_here_value = price[firstcut] + value[L-firstcut];
    if (cut_here_value > max)
      max = cut_here_value
  V[L] = max;


length =  1  2  3  4  5  6  7  8
 price =  1  5  8  9 10 17 18 20
 value =  1  5  8 10 13 17 18 22

--------------------------------------------------------

coins = {  1,  5, 10, 25 }; N = 4 = length of coins
want to give change for A = 22 cents
how many different ways of doing that?

10 + 10 + 1 + 1
10 + 5 + 5 + 1 + 1
10 + 5 + 7*1
10 + 12*1
5 + 17*1
22*1
= 6 ways

ways(A, X) = number of ways of gicing change for A cents
             using coins[0] up to coins[X]

ways(A, X) = ways of making A without using a quarter
           + ways of making A, using a quarter

ways(A, X) = ways of making A without using a quarter
           + ways of making A-25, still allowed to use quarters
             
e.g. ways(63, 4) = ways(63, 3) + ways(38, 4)
     ways(63, 3) = ways(63, 2) + ways(43, 3)
     ways(63, 2) = ways(63, 1) + ways(58, 2)
     ways(63, 1) = ways(63, 0) + ways(62, 1)
     ways(38, 4) = ways(38, 3) + ways(13, 3)
     etc etc etc, a lot of recursions

KEY THING:

Ask whether we will use any quarters at all or not,
only two options:

ways(A, 4) = ways of making A without using a quarter
           + ways of making A-25, still allowed to use quarters

ways(A, X) = if X = 0 => ( if A = 0 then 1
                         ( if A != 0 then 0
             if A < 0 => 0
             else     => ways(A, X-1) + ways(A-coin[X-1], X)

reformulate to avoid negative A's
ways(A, X) = if X = 0 => ( if A = 0 then 1
                         ( if A != 0 then 0
             else if A >= coin[X-1] => ways(A, X-1) + ways(A-coin[X-1], X)
             else                   => ways(A, X-1)

int ways[numcoins][maxamt+1];
ways[0][0] = 1
ways[0][everything else] = 0
for N = 1 to numcoins - 1
  for A = 0 to maxamt
    if A >= coin[N-1] 
      then ways[N][A] = ways[N-1][A] + ways[N, A-coins[N-1]]
      else ways[N][A] = ways[N-1][A]