Dynamic Programming (Part 2)

This post is continuation of the first dynamic programing post. In this post will be looking into a class of optimization problem which can be solved with dynamic programming.

Let’s first see what are some of the approaches to solve optimization problem.

  1. Brute Force : In this approach, basically we are traversing all the paths in the tree. If there are exponential spread of the tree, the solution will lead to an exponential solution. In such problems the number of input which can be solved are really small, normally less than 10, may be even smaller than that. Can use DFS or BFS to explore the paths, and find the minimum/maximum solution across all the paths. Run time of such solution is exponential.

  2. Branch & Bound : This approach is basically a extension of the brute force approach, but rather than traversing all the paths in the graph, some of the paths can pruned based on the heuristics for example the partial path solution solution itself is greater than the previous registered solution when find the minimum solution. With such approach many paths in the problem space, will be cut short rather than exploring till the leaf nodes. In the worst case the solution will still be exponential, but in practice would be a much better solution over brute force, with small optimization.

  3. Greedy : Greedy approach takes the local optimal solution always at each step, assuming that it will lead to a global optimal solution. This approach seems very simple, but often leads to wrong answers for the overall problem. Also in case it seems to work a prove might be needed, which is hard to analyze in interview settings.

  4. Dynamic Programming : Dynamic programming approach seems to work for problems where the optimal sub structure is available and the brute force solution seems exponential due to overlapping sub problems. With the optimal sub structure, defining the correctness of the solution and overlapping sub problems improving the performance of the problem from exponential to polynomial time.

With that let’s see explore optimal sub structure in the problem:

Optimal sub structure property can be defined as: To get the optimal solution for the problem, the selection of the optimal subproblem should be made, which will also be selecting it’s own optimal sub problem to form it’s solution. i.e. If the path from A to C via B is minimum then path from A to B which is minimum in all the paths from A to B, will also be part of the minimum path from A to C via B. Basically it means is that once we find the minimum path from A to B then that path can be extended by adding the edge B -> C to get the minimum path from A to C via B. So to find the overall minimum path from A->C we just need to compare and get minimum path for all the incoming nodes to C and add the cost of the edge from that node to C.

Optimization with ordered selection

In this type of problems basically overall cost is being optimized among various permutations or ordered selections of the paths. There is no condition added to a selection of a certain element in the path. In such types the cost of the ith element is always added along with the optimized cost of the previous sob problems.

This problem is an extension of the climbing stairs problem, where the number of ways which needs to be calculated was done. In this problem it is trying to find the minimum path sum for each of the way to reach the top floor.

def minCostClimbingStairs(self, cost: List[int]) -> int:
    # There are two ways to step on the ith step, the cost at the ith step will be minimum of either of the steps along with the given cost of ith step. This forms the recurrance.
    # mC[i] => min(mC[i - 1], mC[i - 2]) + cost[i]

    # Define data structure to store sub solutions
    n = len(cost)
    # extra one step for the top of the floor
    dp = [0] * (n + 1)

    # fill base case
    dp[0], dp[1] = cost[0], cost[1]

    # iterate over the sub problems in topological order to get ith result
    for i in range(2, n):
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]

    dp[n] = min(dp[n - 1], dp[n - 2])
    # return the last step
    return dp[n]

This is an extension of the unique path problem, which we explored in the previous section. In this problem rather than finding the number of paths, we are looking into find the minimum cost for the path, or the path with the minimum cost.

We need to understand why the optimal sub structure property is true here, considering that if there is a path from (0, 0) to (n - 1, m - 1) through (n , m - 1 ) is minimum then the same path prefix from (0, 0) to (n, m - 1) will also be minimum in all the paths from (0, 0) to (n, m - 1), if that is not the case then some other path prefix is minimum then the initial path which we considered won’t be minimum.

Here we can use the second property of DP which is optimal sub structure to see at the last (n - 1, m - 1) cell if the minimum path sum for (n - 1, m) and (n, m - 1) are already present then we can choose whichever is minimum and add the current cost for cell to achieve the minimum path sum for (n - 1, m - 1).

Now we can fill the for each of the sub solutions first in topological order, to build up the solution for the final result.

def minPathSum(self, grid: List[List[int]]) -> int:
    # define recurrence
    # MinPS(n,m) = min(MinPS(n-1, m), MinPS(n, m - 1)) + grid(n, m)

    # create data structure to store the solutions
    n, m = len(grid), len(grid[0])
    dp = [[0] * m for _ in range(n)]

    # fill base cases
    dp[0][0] = grid[0][0]
    for r in range(1, n):
        dp[r][0] = grid[r][0] + dp[r - 1][0]

    for c in range(1, m):
        dp[0][c] = grid[0][c] + dp[0][c - 1]

    # Iterate over the problems in topological order from left to right, top to bottom.
    for r in range(1, n):
        for c in range(1, m):
            dp[r][c] = min(dp[r - 1][c], dp[r][c - 1]) + grid[r][c]

    # return the solution of the final problem
    return dp[n-1][m - 1]

Optimization with ordered selection with condition

These are special type of optimization problems again based on the ordered selection, but a condition is added for the selection of the ith element in the problem. So the ith sub problem, solution is formed by either considering the ith element cost with previous solution or not considering the ith element cost and only considering the previous sub problem solution and taking optimized result.

def rob(self, nums: List[int]) -> int:
    # recurrence
    # The robber at the ith house has two option, can either rob the house or not rob the house
    # M(i) => Is the max money the robber will make at the ith house
    # M(i) => max(M(i - 1), M(i - 2) + cost(i))
    # If the robber robs the house, it makes money over the house he robbed next to the adjacent
    # If the robber doesn't rob the house then he makes the money from the adjacent house.
    # Robber trying to maximize the gains, will do max of the two.

    # Data structure
    n = len(nums)
    dp = [0] * n

    # base case
    dp[0] = nums[0]
    if n == 1:
        return dp[0]
    dp[1] = max(dp[0], nums[1])

    # iterate over the sub problems
    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

    return dp[n - 1]

This is an extension of the previous problem, where an additional condition was added for the selection for first and last elements of the array. In such cases, it is better to consider selection as two separate cases and handle it separately.

def rob(self, nums: List[int]) -> int:
    # recurrence
    # The robber at the ith house has two option, can either rob the house or not rob the house
    # M(i) => Is the max money the robber will make at the ith house
    # M(i) => max(M(i - 1), M(i - 2) + cost(i))
    # If the robber robs the house, it makes money over the house he robbed next to the adjacent
    # If the robber doesn't rob the house then he makes the money from the adjacent house.
    # Robber trying to maximize the gains, will do max of the two.

    # The recurrence don't change, only thing which is different is that the last house cannot be considered if the first house is part of the solution i.e. robbed, so better to keep both the solutions separately. If we start with first house, only go till n - 1 houses. And if nth house is considered i.e. then don't include the first house in the recurrence.

    # initialize table
    n = len(nums)
    # data store when first house is robbed.
    firstDp = [0] * n
    # data store when last house is robbed.
    lastDp = [0] * n
    if n == 1:
        return nums[0]

    # fill base cases
    firstDp[0] = nums[0]
    firstDp[1] = max(nums[0], nums[1])

    lastDp[n - 1] = nums[n - 1]
    lastDp[n - 2] = max(nums[n - 1], nums[n - 2])

    # iterate sub problems for ith element from front and back.
    for i in range(2, n - 1):
        # iterate over []2 to n - 2] i.e. forwards
        firstDp[i] = max(firstDp[i - 1], firstDp[i - 2] + nums[i])
        # iterate over [n - 3 to 1] i.e. backwards
        lastIdx = n - i - 1
        lastDp[lastIdx] = max(lastDp[lastIdx + 1], lastDp[lastIdx + 2] + nums[lastIdx])

    return max(firstDp[n - 2], lastDp[1])

Optimization with Unordered selection:

Other optimization problems:

In this problem is basically, having a different cost for each of the sub problem. There is optimal sub-structure by reasoning that if any ith day a minimum cost is formed by the minimum cost of i + x day then, then cost at i+x day will be also be minimum. Because if it is not then a new optimal path can be selected for ith day.

At each day, there are three options of buying a pass, and when a x day pass is bought on ith day, the same pass can be applied for the next x number of days. When the pass is applied for i + x days, then cost of those days is not taken and the cost of the ith day is the sum of x day pass + (i + x + 1) day cost, which has already been optimally computed and stored in the table.

Based on that recurrence can be formed as explained in the solution.

def mincostTickets(self, days: List[int], costs: List[int]) -> int:
    # recurrence
    # So at any day in days[i] when travelled, could buy any of the passes.
    # When a pass is bought for the day it covers either that day or next 7 days or next 30 days.
    # So the cost till day till the end of the days will be
    # min of the sum of cost of the pass spent on ith day + cost spent till i + x day based on the pass purchased.
    # minCost[i] => minimum travel cost spent till ith day to the end of the days.
    # minCost[i] => If i is a travel day
    #                   min(minCost[i + 1] + costs[0] # single day pass,
    #                       minCost[i + 7] + costs[1] # seven day pass,
    #                       minCost[i + 30] + cost[2] # thirty day pass)
    #               If i is not a travel day
    #                   minCost[i + 1]

    n = len(days)
    # create table
    lastDay = days[-1]
    maxDays = lastDay + 30
    # 0 index is zero day, so adding one extra day to match 1st index with 1st day
    dp = [0] * (maxDays + 1)

    # iterate the sub problems from the end, as the ith day problem is dependent on the later day problem.
    for _, day in enumerate(reversed(days)):
        # iterate over the non travel days between current day and lastDay in reverse order
        for noTravelDay in range(lastDay - 1, day, -1):
            dp[noTravelDay] = dp[noTravelDay + 1]
        dp[day] = min(dp[day + 1] + costs[0], dp[day + 7] + costs[1], dp[day + 30] + costs[2])
        lastDay = day

    return dp[days[0]]

In the above solution, the days on which the travel is not made contains the same value as i + 1 day cost when the last travel was done. This extra memory, although brings gains in speed for high n, but where the n is small but the values in n are wide spread for example and input array like [1,100,200,365] will create an array of 365 values with most of the values same as the values on which travel was made.

The solution for such can be optimized further to look for only the travel dates. In such case to find out the i+7 and i+30 a simple lookup cannot be done, so we need to iterate from i + 1 index till we find the element outside the day range.

This solution has been covered next. This solution works for lower cases of n where the values are wide spread. Whereas the previous solution works better in time leetcode using more memory, for bigger values of n.

def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        # recurrence
        # So at any day in days[i] when travelled, could buy any of the passes.
        # When a pass is bought for the day it covers either that day or next 7 days or next 30 days.
        # So the cost till day till the end of the days will be
        # min of the sum of cost of the pass spent on ith day + cost spent till i + x day based on the pass purchased.
        # minCost[i] => minimum travel cost spent till ith day to the end of the days.
        # minCost[i] => If i is a travel day
        #                   min(minCost[i + 1] + costs[0] # single day pass,
        #                       minCost[i + 7] + costs[1] # seven day pass,
        #                       minCost[i + 30] + cost[2] # thirty day pass)
        #               If i is not a travel day
        #                   minCost[i + 1]

        n = len(days)
        # create table
        # Add extra day to handle edge conditions
        dp = [0] * (n + 1)

        # no base case

        # iterate the sub problems from the end, as the i th day problem is dependant on the later day problem.
        for i in range(n - 1, -1, -1):
            dayPass = dp[i + 1] + costs[0]

            # iterate over to fetch the sub problem after 7 days
            # At max this will iterate 7 times.
            j = i + 1
            while j < n and days[j] < days[i] + 7:
                j += 1
            sevenDayPass = dp[j] + costs[1]

            # iterate over to fetch the sub problem after 30 days
            # At max this will iterate 30 times.
            k = i + 1
            while k < n and days[k] < days[i] + 30:
                k += 1
            thirtyDayPass = dp[k] + costs[2]
            dp[i] = min(dayPass, sevenDayPass, thirtyDayPass)
        return dp[0]
comments powered by Disqus