举例说明动态规划算法的一个典型应用并写出实现算法

动态规划是一种常用的优化算法，常见的应用场景包括最长公共子序列、背包问题、最短路径等。这里以最长上升子序列为例进行说明。

最长上升子序列问题是指：给定一个无序的整数序列，求出其中的最长上升子序列的长度。

实现算法的思路如下：
1. 定义状态：dp[i]表示以第i个数字结尾的最长上升子序列的长度。
2. 初始状态：dp[i]初始值为1，因为每一个数字都可以看做一个上升子序列。
3. 状态转移方程：当i>j且nums[i]>nums[j]时，dp[i] = max(dp[i], dp[j]+1)。
4. 最终结果：遍历dp数组，取最大值即为最长上升子序列的长度。

代码实现如下：

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int res = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        res = max(res, dp[i]);
    }
    return res;
}

以上代码的时间复杂度为O(n^2)，可以通过二分查找进行优化，时间复杂度为O(nlogn)。