Given a non-empty string str and a dictionary containing a list of unique words, design a dynamic programming algorithm to determine if str can be segmented into a sequence of dictionary words. If str = "algorithm design" and your dictionary contains "algorithm" and "design", your algorithm should answer Yes as str can be segmented as "algorithm design". You may assume that a dictionary lookup can be done in O(1) time.
1. Define (in plain English) subproblems to be solved.
2. Write the recurrence relation for subproblems.
3. Write pseudo-code to compute the optimal value.
4. Compute its runtime complexity in terms of the input size.