算法-动态规划-子序列
子序列问题 是 动态规划 解决的经典问题。
1. 最长递增子序列 (LeetCode 300)
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
思路：
- dp[i]表示以nums[i]为结尾的最长子序列的长度
- 用j遍历0至i-1的元素，如果
nums[i] > nums[j]，则dp[i] = Math.max(dp[i], dp[j]+1)（可以用nums[i]追加在之前的子序列末尾）
class Solution {
// 时间复杂度：O(n^2)
public int lengthOfLIS(int[] nums) {
int result = 1;
int n = nums.length;
// dp[i]表示 以nums[i]结尾的最长子序列长度
int[] dp = new int[n];
for(int i = 0; i<n; ++i) {
dp[i] = 1;
}
for(int i = 1; i<n; ++i) {
for(int j = 0; j<i; ++j) {
if(nums[j] < nums[i])
dp[i] = Math.max(dp[i], dp[j]+1);
}
result = Math.max(result, dp[i]);
}
return result;
}
}