Vinay
BAN USERDynamic Programming solution:
Let Nways(s, n) - number of ways to make sum s with n dices.
Nways(s, n) = Summation{1..a} Nways(s-i, n-1)
Base case:
Nways(s, 1) = 1 if (s<= a && s>0), 0 otherwise.
Edit:
I see lot of new solutions posted are using only recursion. Memoization should be used otherwise the algorithm is very slow.
Recursion with a lookup table for already computed values is the right way to go.
This algorithm has a potential problem ...
Suppose
CatsOutDogs
Answer - Cats Out Dogs
Your answer - Cat ... you don't consider that using cats gives better solution than using the word cat.
Your algorithm greedily selects the smallest next word in the dictionary. thats why this problem is there. If you think more DP can overcome this problem.
Use order statistics ..
find the 999millionth smallest number from the sequence. (which is 1millionth largest ) . This can be done using randomized order statistics algorithm of median of median algorithm (BPFRT)algorithm.
... O(n).
now use it as a pivot and partition the numbers as smaller and larger. The larger set is the output. O(n)
True, Can't find the length. The data could be streamed into linked list.
- Vinay April 29, 2013Insertion sort.