跳转汇总链接
????????动态规划算法汇总链接
2.1 最长递增子序列
????题目链接
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而
不改变其余元素的顺序
。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
-
状态表示
-
本题依旧以 nums 字符串上 i 位置为结尾作为一个状态;
-
dp[i] 表示,以 i 为结尾的所有子序列中,最长的严格递增子序列的长度。
-
状态转移方程
-
初始化
-
填表顺序
-
返回值
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
int maxRet = 1;
for(int i = 1; i < n; i++)
{
for(int j = 0; j < i; j++)
{
if(nums[j] < nums[i])
{
dp[i] = max(dp[j] + 1, dp[i]);
}
}
maxRet = max(maxRet, dp[i]);
}
return maxRet;
}
};
????如果本文对你有些帮助,欢迎???? 点赞 收藏 关注,你的支持是对作者大大莫大的鼓励!!(✿◡‿◡) 若有差错恳请留言指正~~