Dynamic programming and Longest increasing subsequence problem

Understanding Dynamic Programming

Dynamic Programming (DP) is a powerful algorithmic technique used to solve optimization problems by breaking them down into smaller subproblems and storing the solutions to those subproblems to avoid recomputation. To identify if the problem can be solved by DP or not you can look for optimisation keywords in the problem. If the problem is asking to find the max or min or total number of ways then that could be a hint that this problem could be solved by DP. Mostly if you are very comfortable with recursion then DP becomes very easy as in most cases we are optimising the recursive solution using the DP concept.

How Dynamic Programming Works

The basic idea behind dynamic programming is to optimize a complex problem by breaking it down into smaller, simpler subproblems. These subproblems must have the following properties:

Optimal substructure: The optimal solution to the problem can be constructed from optimal solutions to the subproblems.
Overlapping subproblems: The subproblems recur many times and their solutions can be cached and reused to avoid redundant work.

Once we have identified the subproblems and their solutions, we can use an appropriate data structure (such as an array, matrix, or hash table) to store the solutions to the subproblems. This allows us to avoid re-computation, and results in a significant improvement in time complexity.

To get the solution to the subproblem we can use a few step-by-step processes.

expressing the problem in the index if we could
do everything possible to that index
and since that index will be part of the subproblem now this subproblem can be used to solve another subproblem so we will store that in a sum list or matrix, and this is known as memoisation and also a top-down approach.
and since this process is memorizing the recursive solution so we need a base case as well, write the base case. and we are done now.

Dynamic Programming Techniques

There are two main techniques used in DP:

Memoization: This technique involves storing the results of expensive function calls and returning the cached result when the same inputs occur again.
Tabulation: This technique involves building a table in a bottom-up fashion and filling in the entries in the table based on the solutions to the subproblems.

Examples of Dynamic Programming

Longest increasing Subsequence

The Longest Increasing Subsequence (LIS) problem is a classic example of dynamic programming. Given a sequence, find the length of the longest increasing sequence present in it.

Recursive solution:

def lis_recursion(index, prev_index, arr):
   """
    prev index to know if previous value was taken or not, if taken then compare that with current value, current value should be greater than previous value. start with minus one, as initially no value will be taken. prev index will be updated only when another value is taken that justify the condition of increasing sequence. and this happens for all values, so all subsequence is considered.
    """
    if index == len(arr):
        return 0
    max_length = 0 + lis_recursion(index + 1, prev_index, arr)
    if prev_index == -1 or arr[prev_index] < arr[index]:
        max_length = max(max_length, 1 + lis_recursion(index + 1, index, arr))
    return max_length

memoized solution:

def lis(index, prev_index, arr, dp):
    if index == len(arr):
        return 0
    if dp[index][prev_index + 1] != -1:
        return dp[index][prev_index+1]
    max_length = 0 + lis(index + 1, prev_index, arr, dp)
    if prev_index == -1 or arr[prev_index] < arr[index]:
        max_length = max(max_length, 1 + lis(index + 1, index, arr, dp))

    dp[index][prev_index + 1] = max_length
    return dp[index][prev_index + 1]

To know the dimension of the DP matrix just know the dimension of changing variable. In this case, the index goes from 0->len(arr), so the number of rows = n+1 if len(arr) = n, and the prev_index goes from 0 - len(arr)-1 so the number of columns = n. notice that -1 of prev_index is there just to know if any value was taken or not and it is not considered to store value in DP.

Conclusion

Dynamic Programming is a powerful algorithmic technique that is widely used in computer science to solve optimization problems efficiently. By identifying the subproblems and caching their solutions, we can avoid recomputation, resulting in significant time complexity improvements.

Randheer newsletter