浏阳做网站/百度百科官网
在上一篇中，我们了解了什么是DP（动态规划），并且通过DP中的经典问题 "最大子序和"，学习了状态转移方程应该如何定义。在本节中，我们将沿用之前的分析方法，通过一道例题，进一步巩固之前的内容！
01
第300题：最长上升子序列
第300题：给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
本题有一定难度！
如果没有思路请回顾上一篇的学习内容！
不建议直接看题解！
02
题目图解
首先我们分析题目，要找的是最长上升子序列（Longest Increasing Subsequence，LIS）。因为题目中没有要求连续，所以LIS可能是连续的，也可能是非连续的。同时，LIS符合可以从其子问题的最优解来进行构建的条件。所以我们可以尝试用动态规划来进行求解。首先我们定义状态：
dp[i] ：表示以nums[i]结尾的最长上升子序列的长度
我们假定nums为[1，9，5，9，3]
我们分两种情况进行讨论：
如果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数组中的最大值，就是我们要找的答案。
分析完毕，我们绘制成图：
03
Go语言示例
根据分析，得到代码：
1func lengthOfLIS(nums []int) int {2 if len(nums) < 1 {3 return 04 }5 dp := make([]int, len(nums))6 result := 17 for i := 0; i < len(nums); i++ {8 dp[i] = 19 for j := 0; j < i; j++ {
10 //这行代码就是上文中那个 等等等等
11 if nums[j] < nums[i] {
12 dp[i] = max(dp[j]+1, dp[i])
13 }
14 }
15 result = max(result, dp[i])
16 }
17 return result
18}
19
20func max(a, b int) int {
21 if a > b {
22 return a
23 }
24 return b
25}
注：本系列所有教程中都不会用到复杂的语言特性，大家不需要担心没有学过go。算法思想最重要，使用go纯属本人爱好。同时，本系列所有代码均在leetcode上进行过测试运行，保证其严谨性！
课后问题：本题如何进一步优化？
（请评论区留言！挑选一名送礼物～）
温馨提示
浩仔讲算法~
每天一起学习图解漫画算法。
一起刷题，一起成长！
~长按下方二维码进行关注吧~
关注后有资源~