Minimum words in a string given a dictionary
One possible approach to solve this problem is as follows:-

(1) Create a trie of the dictionary for fast matching.

(2) Create a recursive function that does the following:-

(a) Finds all possible prefixes of the current string that are present in the dictionary.

(b) Calls itself recursively with those prefixes removed

Example:- 

Word:- keyboardrocks
Dictionary:- {key,keyboard,keyboardrock,s,board}

f(keyboardrocks)-&gt;f(boardrocks)
                -&gt;f(rocks)
                -&gt;f(s)


(c) Recurse until the string is reduced to an empty string.

(d) The minimum recursion depth will be the required answer.

What can be done to better the runtime complexity?

You can use memoization to remember the minimum number of words that were needed to construct a prefix of length m of the string in an array.

So now, MinWord[1,n]=MinWord[1,x]+findMinWord[x,n]