Today we continue to review a few more dynamic programming problems. We discussed coin counting problem. Let us look at a variation that involves maximum number of ways in which coins can make a sum. We assume an infinite supply of coins and we could this by backtracking.
void CoinCount(ref List<int> coins, ref List<int>change, int amount, int start, int level)
{

for (int I = start; I < amount; I++)

{

for (int j = 1; i < coins.Count() && j <= amount/coins[I]; j++)

{

for (int k = 0; k < j; k++){
       change[level+k] = coins[i];
}

if (change.sum() == amount) Console.WriteLine("{0} with {1} elements", change.ToString(),
change.Count());

if (change.sum() < amount)
      CoinCount( ref coins, ref change, n, start+1, level+j);

for(int k = 0; k <j; k++){
      change[level+k] = 0;
}
}
From all the change set printed, we can find the the total count as the answer.
Note that we cannot apply the knapsack solution to another coin counting problem earlier we cannot apply a top down greedy choice method because we don't have a criteria to decide upfront how to generate a sequence that satisfies the sum.

The dynamic programming approach builds the solution in a bottom up manner. For each of the given denominations, either the denomination is part of the solution or it isn't. If the denomination is part of the solution, then the solution sub problem shrinks the sum otherwise it shrinks the denominations. If the denomination is part of the solution, then it shrinks the sum from any one of 1 to amount/denomination occurrences. Since there are overlapping subproblems, we could do well to reuse already memoize the computations.

We now look at a different problem which is to reconstruct itinerary. Itineraries consist of source destination pairs. They belong to the same traveler so they all connect. Build the itinerary starting with JFK and in the smallest lexical order.

List<string> GetItinerary(List<Tuple<string, string>> segments)
{
 segment.sort(); // based on source airport comparator

var startItem = segments.find("JFK");
segments.Remove(startItem);

var ret = new List<string>(){startItem.Item1, startItem.Item2};
while (segments.IsEmpty() == False)
{
    startItem = segments.find(startItem.Item2);
    ret.Add(startItem.Item2);
    segments.Remove(startItem);
}
return ret;
}

Allocate minimum number of pages to students
N books
Pi pages i = 1 to N
M students
int GetMinPages(int N, int M, List<int>Pi)
{
assert (Pi.Count() == N);
if (N == 0) return 0;
if (M == 0) return INT_MAX;
min = 0;
for (int i =0; i < N/M;i++)
   int val = GetMinPages(N-i+1, M-1, Pi.Range(i+1,N-i+1)) + Pi.Range(0,i).Sum();
   if val < min
      min = val;
return min;
}