673. 最长递增子序列的个数 (opens new window)

1.动规

思路①：开辟二维数组，在第二维数组中同时保存两个信息：

• 以第i个元素结尾的最长递增子序列长度。
• 当前最长递增子序列长度的个数。

因此重置sum子序列长度的个数时，注意不能重置为1，而是插入的前一个子序列的个数。

class Solution {
    int max=1;
    int count=1;
    public int findNumberOfLIS(int[] nums) {
        int[][] dp=new int[nums.length][2];
        dp[0][0]=1;
        dp[0][1]=1;
        for(int i=1;i<nums.length;i++){
            int len=1;
            int sum=1;
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    if(dp[j][0]+1>len){
                        len=dp[j][0]+1;
                        //重置为第j个元素已有的子序列个数
                        sum=dp[j][1];
                    }
                    else if(dp[j][0]+1==len) sum+=dp[j][1];
                }
            }
            dp[i][0]=len;
            dp[i][1]=sum;
            if(len>max){
                max=len;
                count=sum;
            }
            else if(len==max) count+=sum;
        }
        return count;
    }
}