题目描述 ：给定一个未排序的整数数组，找到最长递增子序列的个数。
    示例1：

    输入: [1,3,5,4,7]
    输出: 2
    解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

    思考 ： 动态规划问题
    1、 与最长递增子序列问题的相同之处和差异之处。相同之处：同样需要求出最长递增子序列。差异之处：需要记录最长递增子序列的个数 length[i]。
    2、能否先求解最长递增子序列的 dp[]，然后再计算最长递增子序列的个数？（直观想法：不行，因为 dp[i]只是存放以 nums[i] 结尾的最长递增子序列长度，而在计算 dp[i] 的时候可能会出现多个组合，但是仅有 dp[i] 不足以计算出 length[i]，因此，我们需要在计算 dp[] 的过程中同时更新 length[]）。

    解法：
    1、定义状态转移方程
    dp[i]：以 nums[i] 为结尾的最长递增子序列长度（必须包含 nums[i]）。
    length[i]：以 nums[i] 为结尾的最长递增子序列个数（必须包含 nums[i]）。
    2、动态规划思想
    在原有的最长递增子序列 nums[0,…,j] 中，尝试把 nums[i] 加在 nums[j] 的末尾（此处 i > j）。
    假设 nums[i] > nums[j] 成立，讨论两种情况。

    • 已知原有的最长递增子序列长度为 dp[j]，加上 nums[i] 在末尾，则长度变为 dp[j] + 1，如果 dp[j] + 1 > dp[i]，则说明出现了新的最长递增子序列 nums[0,…,j,i]，即意味着dp[i] 需要更新（即 dp[i] = dp[j] + 1），最长递增子序列个数也需要更新（直观上看，此处的 length[i] 需要置为1，其实不然，虽然说出现了新的最长递增子序列，但是由于 length[i] 的取值依赖于 length[0,,,i-1]，所以此处应该更新为 length[i] = length[j]，直接继承 nums[j] 的状态） 。
    • 如果 dp[j] + 1 == dp[i]，则意味着最长递增子序列长度不发生改变，但是存在多种组合情况，由于 dp[i] 的计算依赖于规模为 O(n) 的子问题，所以在此，dp[] 不进行更新，只更新 length[i]（length[i] += length[j]）。
    • 其实，还存在一种情况：dp[j] +1 < dp[i]，但是这种情况的讨论毫无意义，因此此时的子序列并不是最长递增子序列，可以直接忽略。

    综上所述，给出核心思想如下：

    for i in [0,…,nums.length] for j in [0,… i-1] if nums[i] > nums[j] if dp[j] + 1 > dp[i] dp[i] = dp[j] + 1 length[i] = length[j] else if dp[j] + 1 == dp[i] length[i] += length[j]

    3、初始化和问题求解

    • 动态规划问题中，参数初始化也是一件很重要的事情。在此，dp[]、length[]均初始化为1，即最长子序列的长度最小为1，最长子序列的个数最小为1。
    • 由于题目要求的是最长子序列的个数，需要对 dp[] 进行一次遍历得最长长度（可在计算过程动态方程中获取），然后再根据最长子序列长度去 length 中匹配。

    4、算法评估

    • 时间复杂度：O(n2)。
    • 空间复杂度：O(n)。

    代码 ：

    1. class Solution {
    2.     public int findNumberOfLIS(int[] nums) {
    3.         int n = nums.length;
    4.         int[] dp = new int[n];
    5.         int[] length = new int[n];
    6.         Arrays.fill(dp, 1);
    7.         Arrays.fill(length, 1);
    9.         int max_length = 1; //记录最长子序列长度
    10.         for(int i = 0; i < n; i++){
    11.             for(int j = 0; j < i; j++){
    12.                 if(nums[i] > nums[j]){
    13.                     if(dp[j] + 1 > dp[i]){
    14.                         //说明在原序列[0...j]后面加上nums[i]，得到新的最长子序列
    15.                         //length[i] 直接继承 length[j]的状态
    16.                         dp[i] = dp[j] + 1;
    17.                         length[i] = length[j];
    18.                     }
    19.                     else if(dp[j] + 1 == dp[i]){
    20.                     //说明在原序列[0...j]后面加上nums[i]，刚好组成最长子序列[0...i](已存在)
    21.                     //由于j的取值为[0,...i-1]（i>=1）,则说明可能存在多个j的取值符合此条件，因此需要累加所有情况
    22.                     length[i] += length[j];
    23.                     }
    24.                 }
    26.             }
    27.             max_length = Math.max(max_length, dp[i]);
    28.         }
    29.         int ans = 0;
    30.         for(int i = 0; i < n; i++){
    31.             if(dp[i] == max_length)
    32.                 ans += length[i];
    33.         }
    34.         return ans;
    35.     }
    36. }