刷leetcode-hot100-动态规划3.11
目录
刷leetcode hot100–动态规划3.11
第一题：最长递增子序列[10:53]
1.dp数组及下标含义：
dp[n]:nums[0…n]的最长严格递增子序列长度
【无法进行后续比较】
dp[n]以nums[n]结尾的最长严格递增子序列对应的长度
2.初始化：注意！！ 这里应该初始化为1，因为每一个字符单独拎出来这个子序列长度就是1！！！
3.递推公式：dp[i] = max(dp[j]+1) 当nums[j]<nums[i]（i>j）
4.遍历5.打印数组
注意：： 实际操作时，case:[0]输出了0，因为maxNum没进循环，所以还是0—> 最好对特殊情况if–return提前处理
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
//dp[n]nums[0...n]的最长严格递增子序列长度
//dp[n]以nums[n]结尾的最长严格递增子序列长度
//dp[n]=0,
vector<int> dp(nums.size(),1);//初始化应该是1
//dp[i] = max(dp[j]+1) 当nums[j]<nums[i]
if(nums.size()==1){
return 1;
}//case:[0] -->输出0，因为maxNum是0
int maxNum = 0;
for(int i = 1;i<nums.size();i++){
for(int j = 0;j<i;j++){
if(nums[j]<nums[i]){
dp[i] = max(dp[j]+1,dp[i]);
}
}
maxNum = max(maxNum,dp[i]);
}
return maxNum;//不应该return dp[nums.size()-1]
}
};