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.

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.

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.