Dynamic Programming (Part 1)

Dynamic programming is a problem solving strategy which can help to improve exponential runtime of the algorithm for certain type of problems. In this article, I will go over some of the background of this strategy with examples. In further article of these series, I will go over different type of DP problems I have encountered and templates/strategy to solve them.

The name as dynamic programming for this strategy hides the actual strategy.The strategy can be described as decomposing the problem into sub-problems, using strategies like divide and conquer or decrease and conquer and then solving these sub problems optimally to compose the optimal solution for actual given problem.

The problems where this strategy can be applied, can reduce the time from exponential to polynomial is that the sub problems are often repeated across the problem space, so once the sub-problem is solved then result of the problem is stored in memory and reused there after whenever the same problem is called again.

So even though there can be exponential calls to sub-problems, number of unique sub-problems are often polynomial in number, which can significantly helping in reducing the time complexity. The run time can then be defined as = (number of unique subproblem) * time taken to solve each sub-problem.

DP can be used to solve two kind of problems.

Optimization problems, which are used to minimize or maximize the overall result, which is min/max of the sub problems.
Non-optimization problem, example such counting problems, where the overall result is a count of combinations or permutations calculated as function of the sub problems. Or some problems, where overall problem by definition is defined as a function of smaller sub problems.

Set of problems, where this dp strategy can be applied for optimization have two characteristics:

Optimal sub-structure:

This property is used to define the correctness of the DP algorithm in optimization problem. What this property says is that the optimal sub solution can be selected to make the overall optimal solution. Will discuss more about this property when covering optimization problems.

Overlapping sub problems:

The overlapping sub problem is where the dynamic programming is able to save time by reusing the results already computed rather than computing the results again and again. With this property, there is no repetition of the same path of the recursion tree. Using this property DP can also be described as recursion without repetition. This is the step which helps to compute the run time of such problem by just computing the run time of only unique sub problems.

Methods:

There are two methods to describe the solution and write the implementation of DP problems. Both the methods will have the same time complexity for solving the problem other than constant factor during recursive implementation of top down method. In both these methods the idea is to visualize or describe the problem space in terms of a dependency graph, where the overall problem is dependent on the underlying sub problems.

Top Down method

The top down approach is basically a DFS of the sub problem dependency graph. Where each path is explored till the leaf node, and partial result for nodes are stored in the table(map), in case the node is visited again the partial results are reused from the map rather than exploring the same path again. In that way each path in the graph is only traversed once.

Bottom up method

Bottom up method is basically solving the smaller sub-problems starting from the base cases in the topological order of the dependency graph. These smaller sub problems are starting nodes in the DAG of the dependency graph when sorted topologically. Once these sub problems are solved the solution is stored in a suitable data structure like an array and can be used to compose the solution for the higher level problems. Important thing here is that all the dependent sub problems in the topological order need to be solved before solution can be composed for the overall solution, this defines the order of iteration over the sub problems such that this can be achieved.

I will be focusing on the bottom up approach, as:

For interview setting this approach is easier to implement.
Easier to debug and test, because of no recursive tree.
The time and space complexities are much easier to reason.

Steps for solving DP problem using bottom up approach.

Forming the recurrence to define the problem with decrease/divide and conquer approach.

This is the part which is the most critical & thought engaging part of DP problem solving.
The idea in this part is to define the problem, in the form smaller sub problems this could be smaller problem by 1 or half sub problem. Then defining how to compose the smaller sub problems to form the overall problem. This leads to a recurrence which then needs to be solved as the next step.

Expressing the recursive solution as a bottom up algorithm.

Identifying all the unique sub-problems in the solution.
Creating a dependency graph of the sub problems and understand the topological order for solving the overall problem.
Create a data structure to store the sub problems, and fill the base cases.
Execute the sub-problems in the topological order, storing the results and building up the solutions to the overall problem.

Let’s look at some non optimization problems first:

1-D problems

fibonacci sequence

Fib(n) = Fib(n-1) + Fib(n-2)

More about the complexity of Fibonnaci sequence? How DP can solve the Fibonnaci sequence in O(n) time? More about the two approaches work with the Fibonnaci numbers?

Climbing Stairs

This one is a problem form of the Fibonnaci series problem as it forms the same recurrence.

def climbStairs(self, n: int) -> int:
    # recurrence
    # ways[i] : Number of ways to reach ith step.
    # Can reach the ith step by either climbing 1 step from the previous step or climbing 2 steps from the i-2 step. This means total ways will some of the two ways.
    # ways[i] => ways[i - 1] + ways[i - 2]
    if n == 1:
        return 1
    # define data structure to store the sub solution.
    dp = [0] * (n)

    # fill base case
    # 0th index is the first step
    dp[0], dp[1] = 1, 2

    # iterate over the solutions in topological order from bottom to top
    for i in range(2, n):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n - 1]

The above solution brings down the time complexity to O(n) from the exponential time for traversing the overall fibonnaci graph with repeating work. The space complexity is O(n) this can be brought down further, by observing that ith solution only needs last two sub problem solutions. So need to just remember those when iterating over the loop, and the space can be brought down to O(1). Given below a solution to do that.

pseudo polynomial#

Here I want to discuss about the complexity in terms of N. So when the term O(N) is being used for these problems, N represents the magnitude or value of input, rather that size of input. This different from problems where N is represented as size of input for example N is the size of input array in sorting algorithm. So to be technically correct the algorithm is polynomial in the magnitude of the input N, but if we use size of the input in terms of bit, it would be log N bits i.e. b. In such case N = 2**b so the algorithm is actually exponential in the size of the input. i.e. O(N) == O(2**b). Such algorithms are referred to as pseudo polynomial algorithm. They are polynomial in terms of value of input but an apple to apple comparison using the size of the input these algorithms are actually exponential.

What it means: It means that if the input is increased such for example N > 2**15 such algorithms will time out, as an exponential algorithm where the size of input len(array or string) > 15.

This further optimization in the space is a natural extension for many DP problems, built on the idea that for any ith sub problem solution, need to only store the solutions for the sub problem on which ith problem is dependent upon!

def climbStairs(self, n: int) -> int:
    # recurrence
    # ways[i] : Number of ways to reach ith step.
    # Can reach the ith step by either climbing 1 step from the previous step or climbing 2 steps from the i-2 step. This means total ways will some of the two ways.
    # ways[i] => ways[i - 1] + ways[i - 2]
    oneStepWays = 1
    twoStepWays = 2
    if n == 1:
        return oneStepWays
    for i in range(2, n):
        ways = twoStepWays
        twoStepWays = oneStepWays + twoStepWays
        oneStepWays = ways
    return twoStepWays

Domino & Tromino Tiling

2-D problems

n choose k selection

def uniquePathsWithObstacles(self, oG: List[List[int]]) -> int:
        # Define recurrence
        # UP(n,m) => 0 if oG(n,m) == 1
        # else
        # => UP(n-1, m) + UP(n, m - 1)
        if oG[0][0] == 1:
            return 0
        # create a data structure to store the result
        n, m = len(oG), len(oG[0])
        dp = [[0] * m for _ in range(n)]
        # fill the base case      
        dp[0][0] = 1

        for i in range(1, n):
            if oG[i][0] == 1:
                break
            dp[i][0] = dp[i - 1][0]

        for j in range(1, m):
            if oG[0][j] == 1:
                break
            dp[0][j] = dp[0][j - 1]
        # fill the rest of the table, in topological order of the dependent sub problem.
        for i in range(1, n):
            for j in range(1, m):
                if oG[i][j] != 1:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

        return dp[n-1][m-1]

Knight Dialer

mod = 10**9 + 7
class Solution:
    def knightDialer(self, n: int) -> int:
        # Using symmetry, we can see that state 4 & 6 are same as well as 2, 8 are same as well as 1, 7 and 3 & 9 are same.
        # So we can calculate only one of them and multiple by 2 as an optimization.
        # kD(0, n) => 2 * kD(4, n - 1)
        # kD(1, n) => kD(4, n -1) + kD(2, n - 1)
        # kD(2, n) => kD(1, n - 1) + kD(3, n - 1)
        # kD(3, n) => kD(4, n - 1) + kD(2, n - 1)
        # kD(4, n) => kD(0, n - 1) + 2 * kD(3, n - 1)

        # TS(n) = 2 * sum(kD(i, n) for i in range(5))
        if n == 1:
            return 10
        # 5 * n matrix, optimized to 5 * 2 also (constant space), rather than using n columns.
        dp = [[1, 0] for _ in range(5)]
        for i in range(2, n + 1):
            # If i odd use 0 column, if i even use 1 column
            prev = i % 2
            col = (i + 1) % 2
            dp[0][col] = 2 * dp[4][prev]
            dp[1][col] = dp[4][prev] + dp[2][prev]
            dp[2][col] = dp[1][prev] + dp[3][prev]
            dp[3][col] = dp[4][prev] + dp[2][prev]
            dp[4][col] = dp[0][prev] + 2 * dp[3][prev]

        sol = 0
        # If n odd use 0 column, if n even use 1 column
        res = (n + 1) % 2
        for i in range(1, 5):
            sol = (sol + 2 * dp[i][res]) % mod
        sol = (sol + dp[0][res]) % mod
        return sol