Dynamic Programming - Minimize the Number of Canoes to Take Kids (Google Interview Question)

1. Problem Description
This is a Google interview question for software engineer from careercup. Here  is the original thread of this problem,

"If a canoe can hold 2 kids and a max weight of 150 lbs, write a function that returns the minimum number of canoes needed, given a list of kids and their weights."

2. Analysis
Some of contributors have already proposed a very good solution for this problem. It is to sort the weight - the lightest on one end and the heaviest on the other. Then try to pair the lightest and the heaviest. If the sum of two weights is not greater than the load of boat, then these two share one canoe. Otherwise the heaviest uses one canoe and move towards the middle. Then consider the lightest with the 2nd heaviest. Repeat this process until exhaust the list of weight.

I believe that this is the best solution so far and my solution proposed in this blog can't do better than this. However it will think about this problem in a different angle and try to use dynamic programming to solve this problem.

The following picture shows the mathematical formulation and constraints, and the sub-problem.

Constraints and Sub-problem

Corner cases:
    - N = 2, if the sum of two weights > 150, then f(2) = 2 otherwise f(2) = 1
    - N= 1, f(1) = 1

3. Implementation Discussion
Caching 
As usual I was trying to cache the result of the sub-problems. But unfortunately I fail to do so, because I can't find the good key for hash map that can represent the sub-problem uniquely. The sub-problem consists of a list o f weights with the list size from 1 to N-1. The candidate of the key would be either the list of indices of kids remaining in the sub-problem or the actual weights remaining in the sub-problem. Therefore the key would be a list/vector.This is really not a good solution in this case.

Sorting
Sorting should also benefit this solution. Because it will limit the number of sub-problems. As long as found the pair whose weight is greater than the load of the canoe, then can stop trying the rest of sub-problems because we already have a solution as good as the best of the rest. The following picture shows the sub-problem after sorting.

Sub-problem after Sorting