思路
状态定义：dp[i]表示在数组nums中以第i位置为结尾的最长上升子序列
转移方程：
在计算dp[i]之前，我们通过计算，已知dp[0]......dp[i-1]的值
由于dp[i-1]代表以i-1结尾的最长上升序列
则，当nums[i]>nums[i-1]时，有几率形成更长的上升序列
只需要将当前nums[i]分别并入dep[0......i-1]中，看是否能形成更优序列即可
即当前i依赖比i小的O(n)个子问题
故，转移方程为：dp[i] = max(dp[0......i-1])+1
初始状态：
由于至少存在一个元素使得dp[i]满足子序列，故初始为1
边界：
nums[i]>nums[i-1]
实现
（外层循环确定范围，内层循环做子问题最优解合并）
目录[https://www.jianshu.com/p/85e18c21317a] 题号[https://lee...
零钱问题 背包问题 最长公共子序列 最长公共子串 最长上升子序列 最大连续子序列和
最长公共子序列 最长上升子序列 最长公共上升子序列
1、最长公共子串 2、最长上升序列 （国王建设道路问题也是最长上升序列） 3、添加最少的字符实现回文串。 4、从头...
70. 爬楼梯 5. 最长回文子串 300. 最长上升子序列
目录[https://www.jianshu.com/p/85e18c21317a] 题目[https://lee...
1 最长无重复字符子串 2 最长上升子序列（动态规划） 3 最长公共子序列的长度（动态规划） 4 对于一个字符串，...
题目 LeetCode300. 最长上升子序列 解析 与最长连续升序子串[https://www.jianshu....
给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。 说明 最长上升子序列的定义： 最长上升子序列问...
题目 给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。 说明最长上升子序列的定义：最长上升子序列...
本文标题：DP--最长上升子序列（线性-单串）
本文链接：https://www.haomeiwen.com/subject/rshfkrtx.html
网友评论