Solving the Longest Increasing Subsequence and Coin Change problems using DP.
The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, in the sequence {10, 22, 9, 33, 21, 50}, the LIS is {10, 22, 33, 50}, and its length is 4. This problem can be solved with a classic DP approach in O(n^2) time. We use a DP array `dp[i]`, which stores the length of the LIS ending at index `i`. To compute `dp[i]`, we look at all previous elements `j < i` and if `arr[j] < arr[i]`, we can potentially extend the LIS ending at `j`. So, `dp[i]` becomes `1 + max(dp[j])` for all such `j`. An even more efficient O(n log n) solution also exists. The Coin Change problem asks for the minimum number of coins required to make a certain amount of change, given a set of coin denominations. This is another classic DP problem where `dp[i]` stores the minimum number of coins needed to make amount `i`. The state transition is `dp[i] = 1 + min(dp[i - coin])` for all available coin denominations `coin <= i`. Both problems are excellent for practicing DP formulation.