673. 最长递增子序列的个数 - Java 动态规划

原题地址：https://leetcode.cn/problems/number-of-longest-increasing-subsequence/

题解

这题在300. 最长递增子序列 的基础上还要求求出最长递增子序列的个数

沿袭在最长递增子序列中的题解思路，先用一样的代码求出dp[i]——以nums[i]结束的最长子序列长度

用一个新的数组seqAmt，设seqAmt[i]为以nums[i]结束的最长子序列的个数，可以得出：

设以nums[i]结束的最长子序列的长度dp[i]

则以nums[i]结束的最长子序列的个数seqAmt[i]为满足下列条件的最长子序列个数之和：

• 长度为dp[i]-1
• 该子序列的末尾nums[j]<nums[i]

即：

优化：

同300. 最长递增子序列 ，我们可以在j的遍历条件上进行一些优化

当j遍历到j+1<dp[i]-1时，nums[0]——nums[j]的长度+1小于dp[i]-1，已经无法满足dp[j]==dp[i]-1的情况，可以直接跳出循环

时间复杂度：O(N^2)

空间复杂度：O(N)

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int[] dp=new int[nums.length];
        int[] seqAmt=new int[nums.length];
        int max=0,cnt=0;
        for(int i=0;i<nums.length;i++){
            dp[i]=1;
            for(int j=i;j>=0&&j+1>=dp[i];j--){
                if(nums[j]<nums[i]&&dp[j]+1>dp[i]){
                    dp[i]=dp[j]+1;
                }
            }
            if(max<dp[i]){
                max=dp[i];
            }
        }
        for(int i=0;i<dp.length;i++){
            if(dp[i]==1){
                seqAmt[i]=1;
            }else{
                for(int j=i;j>=0&&j+1>=dp[i]-1;j--){
                    if(nums[j]<nums[i]&&dp[j]==dp[i]-1){
                        seqAmt[i]+=seqAmt[j];
                    }
                }   
            }
            if(dp[i]==max){
                cnt+=seqAmt[i];
            }
        }
        return cnt;
    }
}