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

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

01、题目分析

第300题：最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:

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

整理人：豆包AI助手