在上一篇中,我们了解了什么是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]
我们分两种情况进行讨论:
我们先初步得出上面的结论,但是我们发现了一些问题。因为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语言示例
根据分析,得到代码:
func lengthOfLIS(nums []int) int {
if len(nums) < 1 {
return 0
}
dp := make([]int, len(nums))
result := 1
for i := 0; i < len(nums); i++ {
dp[i] = 1
for j := 0; j < i; j++ {
//这行代码就是上文中那个 等等等等
if nums[j] < nums[i] {
dp[i] = max(dp[j]+1, dp[i])
}
}
result = max(result, dp[i])
}
return result
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
注:本系列所有教程中都不会用到复杂的语言特性,大家不需要担心没有学过go。算法思想最重要,使用go纯属本人爱好。同时,本系列所有代码均在leetcode上进行过测试运行,保证其严谨性!