DP 第三讲 - 最长上升子序列

在上一篇中,我们了解了什么是DP(动态规划),并且通过DP中的经典问题 “最大子序和”,学习了状态转移方程应该如何定义。在本节中,我们将沿用之前的分析方法,通过一道例题,进一步巩固之前的内容!

01、题目分析

第300题:最长上升子序列
给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

  1. 输入: [10,9,2,5,3,7,101,18]
  2. 输出: 4
  3. 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4

说明:

  • 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。

这道题有一定难度哦!如果没有思路请回顾上一篇的学习内容! 不建议直接看题解!

02、题目图解

首先我们分析题目,要找的是最长上升子序列(Longest Increasing Subsequence,LIS)。因为题目中没有要求连续,所以LIS可能是连续的,也可能是非连续的。同时,LIS符合可以从其子问题的最优解来进行构建的条件。所以我们可以尝试用动态规划来进行求解。首先我们定义状态:


dp[i] :表示以nums[i]结尾的最长上升子序列的长度

我们假定nums为[1,9,5,9,3],如下图:

PNG

我们分两种情况进行讨论:

  • 如果nums[i]比前面的所有元素都小,那么dp[i]等于1(即它本身)(该结论正确)
  • 如果nums[i]前面存在比他小的元素nums[j],那么dp[i]就等于dp[j]+1(该结论错误,比如nums[3]>nums[0],即9>1,但是dp[3]并不等于dp[0]+1)


我们先初步得出上面的结论,但是我们发现了一些问题。因为dp[i]前面比他小的元素,不一定只有一个!

可能除了 nums[j],还包括 nums[k],nums[p] 等等等等。所以 dp[i] 除了可能等于 dp[j]+1,还有可能等于 dp[k]+1,dp[p]+1 等等等等。所以我们求 dp[i],需要找到 dp[j]+1,dp[k]+1,dp[p]+1 等等等等 中的最大值。(我在3个等等等等上都进行了加粗,主要是因为初学者非常容易在这里摔跟斗!这里强调的目的是希望能记住这道题型!) 即:


dp[i] = max(dp[j]+1,dp[k]+1,dp[p]+1,…..)
只要满足:
nums[i] > nums[j]
nums[i] > nums[k]
nums[i] > nums[p]
….


最后,我们只需要找到dp数组中的最大值,就是我们要找的答案。

分析完毕,我们绘制成图:

PNG

03、Go语言示例

根据以上分析,可以得到代码如下:

  1. func lengthOfLIS(nums []int) int {
  2. if len(nums) < 1 {
  3. return 0
  4. }
  5. dp := make([]int, len(nums))
  6. result := 1
  7. for i := 0; i < len(nums); i++ {
  8. dp[i] = 1
  9. for j := 0; j < i; j++ {
  10. if nums[j] < nums[i] {
  11. dp[i] = max(dp[j]+1, dp[i])
  12. }
  13. }
  14. result = max(result, dp[i])
  15. }
  16. return result
  17. }
  18. func max(a, b int) int {
  19. if a > b {
  20. return a
  21. }
  22. return b
  23. }