0. Problem

If you try writing this recursively, you'll quickly find that in order to write a recursion, you need to know the largest number in the subsequence you're considering. You can do this by designing the function in a way so you know the last element in your subsequence.

To do this, you can write a function lenLIS(i) that computes the length of the LIS that ends with nums[i].

1. Recursion

To write this recursively, you know the subsequence ends with the number at i. Before that number in the subsequence, you can have any other subsequence come first, as long as it ends with a number less than nums[i]:

2. Base case

The length of the the sequence 0...0 is just 1.

3. Code

To code this up, you can use Tabulation. To do this, you should realize that lenLIS depends on lenLIS of bigger $\tt i$ and $\tt j$. This means you can compute lenLIS for the largest i and j first, and smallest indexes last. We'll store the results in a 2D array. Here's the code:

Time Complexity $O(n^2)$. The double for loop is $n^2$ and the max(lenLIS) is $O(n)$.

Space Complexity $O(n)$ for lenLIS.

It turns out Dynamic Programming isn't the most optimal solution to this problem. The most optimal solution is a trick, which we cover later in Tricks. But DP is good practice anyway, and the trick is very difficult to come up with during an interview.