Space optimization
Lesson 12 of 15 in Coddy's Dynamic Programming 101 course.
In dynamic programming, we often use a table or matrix to store solutions to subproblems. However, in some cases, the size of the table can be too large and consume too much memory. This is where space optimization comes in. Space optimization techniques are used to reduce the memory required to solve a dynamic programming problem.
One popular space optimization technique is using rolling arrays, also known as sliding arrays. Instead of storing the entire table, only a portion of it is stored at a time, and the previous values are discarded as new values are computed. This can significantly reduce the memory required to solve a problem.
Challenge
HardIn this challenge, you are given an array of integers. Your task is to find the length of the longest increasing subsequence (LIS) in the array. An increasing subsequence is a sequence of numbers in the array where each number is larger than the previous number. The LIS is the longest such subsequence. You must implement the solution using space optimization techniques.
Try it yourself
def lis_length(arr):
# Write code hereAll lessons in Dynamic Programming 101
3Dynamic programming algorithms
Longest common subsequenceKnapsack problemCoin change problemEdit distance