动态规划简明教程 - 4
内容提要
本文介绍了动态规划在求解最长递增子序列问题中的应用。给定一个整数数组，目标是找到其中最长严格递增子序列的长度。通过暴力搜索、记忆化搜索和动态规划三种方法逐步优化算法，动态规划的核心在于定义状态转移方程，利用已知子序列长度计算当前元素的最长子序列长度，从而实现高效求解。
延伸解读
从暴力到动态规划的优化路径
文章展示了解决最长递增子序列问题的三种方法：暴力搜索、记忆化搜索和动态规划。暴力搜索通过回溯穷举所有递增子序列，但存在大量重复计算，导致超时。记忆化搜索引入备忘录记录已计算的元素组合，避免重复，但性能仍较低。动态规划则自底向上，定义状态转移方程，高效求解。这种循序渐进的方式有助于理解动态规划的思想。
动态规划状态定义与转移
动态规划解法的核心是定义状态：dp[i]表示以nums[i]结尾的最长递增子序列长度。转移时，遍历j从0到i-1，若nums[j] < nums[i]，则dp[i] = max(dp[i], dp[j]+1)。初始dp[i]=1。最终答案是dp数组中的最大值。这种自底向上的方法避免了递归开销，时间复杂度为O(n^2)。
记忆化搜索的备忘录设计
记忆化搜索使用二维数组memo记录不同prev和cur组合的结果，其中memo[prev+1][cur]存储从prev和cur开始的最长递增子序列长度。递归过程中，若memo[prev+1][cur]已计算则直接返回，否则计算并存储。这消除了暴力搜索中的重复子问题，但空间复杂度较高，且递归深度可能较大。
Q&A
动态规划如何应用于最长递增子序列问题？
动态规划通过定义状态转移方程，利用已知子序列长度计算当前元素的最长子序列长度，从而高效求解。
暴力搜索方法的时间复杂度如何？
暴力搜索方法的时间复杂度较高，因为它尝试找出所有可能的递增子序列，导致重复计算。
记忆化搜索是如何优化暴力搜索的？
记忆化搜索通过备忘录记录已检测过的元素组合，避免重复计算，从而提高效率。
动态规划的状态转移方程是什么？
状态转移方程为 F(i) = max{F(i), F(j) + 1}，其中 j < i 且 nums[j] < nums[i]。
如何实现动态规划算法来求解最长递增子序列？
通过建立一维数组 dp，遍历数组并更新以每个元素结尾的最长子序列长度，最终返回最大值。
最长递增子序列的示例是什么？
例如，对于输入 [10,9,2,5,3,7,101,18]，最长递增子序列为 [2,3,7,101]，长度为 4。
