1     public int findNumberOfLIS(int[] nums) { 2         int n=nums.length; 3         if(n==0||n==1)return n; 4         int []dp=new int[n]; 5         int []cnt=new int[n]; 6         int i,j,max=0,res=0; 7         Arrays.fill(dp, 1); 8         Arrays.fill(cnt, 1); 9         for(i=1;i
     
      nums[j]&&dp[i]<=dp[j]){12                     dp[i]=dp[j]+1;13                     cnt[i]=cnt[j];14                 }else if(nums[i]>nums[j]&&dp[i]==dp[j]+1)15                     cnt[i]+=cnt[j];16             }17           max=Math.max(dp[i],max);18         }19         for(i=0;i
     

   首先要清楚dp[i]存放的是什么。之前想当然的认为dp[i]=0..i最长的自增子序列长度，若是如此，那么dp[]便为非降序数组，然而事实并非如此。通过查看dp[]的增长方式便知，其需要满足两个条件nums[i]>nums[j]&&dp[i]<=dp[j]，关键的是dp[i]<=dp[j]，若没有这个条件，在多次迭代后会有许多重复计算。而最长子序列个数的增长是建立在所有前序状态上的，也就是组合的思想。当nums[i]>nums[j]&&dp[i]==dp[j]+1时，也就是再一次满足了最长子序列的条件，但是并不改变当前dp[i]的值（避免多重计算）此时，当前最长子序列增长。