Dynamic Programming Algorithms

Dynamic programming stores and reuses previously computed subsolutions in a table to eliminate redundant work. It's the classic memoization example, pulling naive recursion from O(2^n) down to O(n).

Finds the length of the longest increasing subsequence you can pick while preserving order. dp[i] is defined as the subsolution 'length of the LIS ending at element i', and reusing the subsolutions of earlier, smaller elements pulls the O(2ⁿ) brute force down to O(n²).