How can Dynamic Programming be used to solve the Longest Increasing Subsequence Size problem?

Dynamic Programming can be used to solve the Longest Increasing Subsequence Size problem by breaking it down into smaller subproblems and using the solutions of these subproblems to build the solution for the larger problem.

The Longest Increasing Subsequence (LIS) problem involves finding the length of the longest subsequence in a given array of integers, where the subsequence is in increasing order.

To solve this problem using Dynamic Programming, we can define an array dp[] of the same length as the input array, where dp[i] represents the length of the longest increasing subsequence ending at index i.

We initialize all elements of dp[] to 1, as the minimum length of any subsequence is 1 (including just the element itself).

Then, for each index i from 1 to n-1 (where n is the length of the input array), we iterate through all previous indices j from 0 to i-1. If the element at index i is greater than the element at index j, we update dp[i] as the maximum of dp[i] and dp[j] + 1. This means that if the element at index i can be included in the increasing subsequence ending at index j, we update the length of the increasing subsequence ending at index i.

Finally, we find the maximum value in the dp[] array, which represents the length of the longest increasing subsequence in the given array.

Here is the step-by-step process:
1. Initialize an array dp[] of length n, where n is the length of the input array.
2. Set all elements of dp[] to 1.
3. Iterate through each index i from 1 to n-1.
4. For each index i, iterate through all previous indices j from 0 to i-1.
5. If the element at index i is greater than the element at index j, update dp[i] as the maximum of dp[i] and dp[j] + 1.
6. Find the maximum value in the dp[] array.
7. The maximum value represents the length of the longest increasing subsequence in the given array.

The time complexity of this approach is O(n^2), where n is the length of the input array.