Hey Folks,

I tried a DFS approach with DP and the below solution gets accepted in Leetcode. However, it's pretty slow and i am trying to understand the bottleneck. Please correct me if i am wrong on the time complexity which i think is O(n^2) in this case.

```
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[] dp = new int[nums.length];
int max = 0;
for (int i = 0; i<nums.length; i++) {
max = Math.max(max, solve(nums, i, dp));
}
return max;
}
int solve(int[] nums, int start, int[] dp) {
if (dp[start] != 0) return dp[start];
int max = 1;
for (int i = start + 1; i<nums.length; i++) {
if (nums[i] > nums[start]) {
int len = 1 + solve(nums, i, dp);
max = Math.max(max, len);
}
}
dp[start] = max;
return max;
}
}
```