1D Memoization in Recursive solution of Longest Increasing Subsequence

Question

Calculating LIS (Longest Increasing Subsequence) in an array is a very famous Dynamic Programming problem. However in every tutorial they first show the recursive solution without using the concepts of DP and then solve it by applying Bottom-Up DP (Iterative Solution).

My question is:

How will we use Memoization in Recursive Solution itself. Not just Memoization but memoization using 1D array.

I did some research but could not find anything of relevance. Although there are 2 places where recursive memoization has been asked 1 & 2 but the solutions over there, are using 2D Map / Array for memoization.

Anyway Memoizing the solution with 1D array, is giving wrong output. Here is what I did:

int lis(int idx, int prev)
{
    if(idx >= N)
        return 0;

    if(dp[idx])
        return dp[idx];

    int best_ans = lis(idx+1, prev);

    int cur_ans = 0;
    if(arr[idx] > prev)
    {
        cur_ans = 1 + lis(idx+1, arr[idx]);
    }
    int ans = max(best_ans, cur_ans);
    dp[idx] = ans;
    return ans;
}

int main()
{
    // Scan N 
    // Scan arr

    ans = lis(0, -1));
    print ans;
}

Although I know the reason why this solution is giving Wrong output as:

There can be more than one solution for the giving index based on what was the previous value.

But I still want to know how it can be done using 1D array.

I am curious to know the solution because I have read that every DP Top-Down solution can be reframed into Bottom-Up and vice-versa.

It would be highly helpful if someone could provide some insight for the same.

Thanks in advance.

Yettie

Can someone please explain this question I am confused with same problem? – Uncircumcised

Answer 1

This can't be done because the problem fundamentally needs a 2D data structure to solve.

The bottom-up approach can cheat by producing one row at a time of the data structure. Viewed over time, it produces a 2D data structure, but at any given time you only see one dimension of it.

The top-down approach has to build the entire 2D data structure.

This is a fundamental tradeoff in DP. It is usually easier to write down the top-down approach. But the bottom-up approach only has to have part of the overall data structure at any time, and therefore has significantly lower memory requirements.

Terrier

Thanks for the answer. And yes you are very right. I have particularly seen the cases when top-down memoization space requirements are more than that of bottom-up. Although in most of them it gets pretty visible why this is being done, as there remains no longer requirement of the above rows, but still there are some cases where this is not intuitive. Can you further explain what is the insight for the same? Moreover, I would like to know why the top-down approach can not be used to gain this utility. Also plz explain with respect to LIS problem. – Yettie

@ShivangBansal The reason is that recursion+memoize doesn't know when a particular piece of data will never be needed again, so has to keep it all. In bottom up you can know when you're actually done with a piece of data because you've moved on through your data. If that doesn't make intuitive sense, I could write an essay and it wouldn't help until you see it for yourself. – Terrier

@Terrier are there any hints from the sub problem that indicate the use of a 2d instead of a 1d? For a person like my self just getting into dynamic programming, I can see the sub problems of this problem and know intuitively that if I can cache them I won't have to work on them and just to re-use them so why does not using a 1d work for this particular problem not work? Any additional explanation is helpful please. – Eonian

@Eonian I have no better explanation than, "Try to write a recursive function, look at how many arguments are needed to make the function work properly." Actually doing several problems will do more good than a book of explanations. – Terrier

Answer 2

def LongestIncreasingSubsequenceMemo(nums, i, cache):
    if cache[i] > 0:
        return cache[i]
    result = 1
    for j in range(i):
        if nums[i] > nums[j]:
            result = max(result, 1 + LongestIncreasingSubsequenceMemo(nums, j, cache))
    cache[i] = result
    return result

def main():
    nums = [1,2,3,4,5]
    if not nums:
        return 0        
    n = len(nums)
    cache = [0 for i in range(n)]
    result = 1
    for i in range(n):
        result = max(result, LongestIncreasingSubsequenceMemo(nums, i, cache))
    return result

if __name__ == "__main__":
    print(main())

In the above solution, we are taking a one-dimensional array and updating it for each element in the array.

Downhearted

Answer 3

This can be done and there is no requirement for a 2d array. Because we need to find the max LIS ending at every index So if we calculate LIS for the element at arr[0], instead of calculating again and again we calculate once and store it in DP[1].

If we calculated LIS for {arr[0],arr[1]} then we store the result in DP[2] and so on until the DP[n]. See the code below to understand this fully.

Memoization of the recursive code

above code got accepted on gfg as well

Beitch

Please provide additional details in your answer. As it's currently written, it's hard to understand your solution. – Restaurateur

Welcome to Stack Overflow. Please don't post screenshots of text. They can't be searched or copied, or even consumed by users of adaptive technologies like screen readers. Instead, paste the code as text directly into your question. If you select it and click the {} button or Ctrl+K the code block will be indented by four spaces, which will cause it to be rendered as code. – Legitimist