动态规划最长递增子列

动态规划最长递增子序列问题描述的是在一个已知序列中，取出若干元素组成一个新的序列，要求新序列中的元素顺序保持不变且递增，找出最长的这样的子序列。为了解决这个问题，可以采用动态规划的思路。

首先，定义一个dp数组，dp[i]表示以第i个元素作为末尾的最长递增子序列的长度。那么，我们要求的最长递增子序列的长度就是dp数组中的最大值。

接下来，我们需要确定dp数组的递推关系。可以采用以下的递推公式：
dp[i] = max(dp[j] + 1)，其中j < i且nums[j] < nums[i]。

这个递推公式的意思是，以第i个元素作为末尾的最长递增子序列的长度，等于在前面的元素中找到一个小于nums[i]的元素，使得以该元素作为末尾的最长递增子序列的长度加上1，得到的结果最大。也就是说，我们要找到一个在i之前的位置j，使得dp[j]最大，并且nums[j] < nums[i]。

通过计算dp数组中的每个元素，最后得到的dp数组中的最大值即为最长递增子序列的长度。

总结起来，动态规划最长递增子序列的思路是：先定义dp数组的含义，然后确定dp数组的递推关系，最后计算dp数组中的最大值即为最长递增子序列的长度。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* [动态规划——最长递增子序列](https://blog.csdn.net/qq_36935691/article/details/113924931)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *3* [动态规划系列之「最长递增子序列」](https://blog.csdn.net/weixin_44471490/article/details/109030232)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]