Dynamic Programming

Dynamic programming problems are similar to the divide-and-conquer problems with one important difference: The subproblems in divide-and-conquer are distinct and disjoint, whereas in the case of dynamic programming, the subproblems may overlap with one another. Also, dynamic programming problems can be solved in a bottom-up fashion instead of just a top-down approach.

Computing Fibonacci numbers is a textbook example of a dynamic programming problem. Furthermore, dynamic programming problems are usually optimization problems, and there may be several optimal solutions. However, the value of the optimal solution will be same.

The word "programming" in dynamic programming doesn't mean coding in the literal sense; in fact, it was used to mean a tabular solution.

Since dynamic programming problems involve subproblems that are overlapping or common, the answer to these subproblems can be stored in a table and reused when needed. This approach is called memoization and avoids the need to recompute the answer to subproblems each time they are encountered.

The scope of this text is limited to teaching evaluation of time and space complexities for various algorithms categories. Therefore, we'll restrict ourselves to one simple DP problem example and slice and dice it various ways to understand how complexity can be worked out for DP class of algorithms.

String Sum Representation

You are provided a positive integer n and asked to construct all strings of 1s, 2s, and 3s that would sum up to n. For example,

if n = 3, then the following strings will sum up to n:

• 111
• 12
• 21
• 3

Solution

Think of 1s, 2s, and 3s as building blocks to construct n. Let's say we pick 1 as the first block. If we know how many strings can represent the integer (n-1), we can deduce that the same number of strings can also represent n, as prefixing 1 to the strings making up the integer n-1 would make up n. This leads to a recursive solution, where we ask ourselves how many strings can sum up to integers n-1, n-2, and n-3? We can prefix those strings with 1, 2, ...