辛星Java动态规划教程第六篇:求最长递增子序列(LIS)的个数，时间复杂度O(n^2)_10 51 2 3 4 5 6 7 8 9 10求递增子序列个数

对于一个固定的序列来说，其最长递增子序列的长度是确定的，但是这样的最长递增子序列有多少个呢？这是一个值得思考的问题。

先来看一个具体的问题吧，比如对于序列{1, 2, 5, 4, 7}来说，我们很容易知道，这个最长子序列有两个，即{1,2,5,7}和{1,2,4,7}。这里的裂变点，在于小于7的时候的最长递增子序列有两个。

如果还不清楚，可以再看一个例子，比如序列 {1, 2, 5, 4, 7, 6, 9, 8, 10} 来说，它的递增子序列有八个，即:
1,2,5,7,9,10
1,2,5,6,9,10
1,2,4,7,9,10
1,2,4,6,9,10
1,2,5,7,8,10
1,2,5,6,8,10
1,2,4,7,8,10
1,2,4,6,8,10
对于10这个元素来说，它是要把所有比它小的最长子序列个数加起来，即以9结尾的最长递增子序列的个数和以8结尾的最长递增子序列的个数。
而以9结尾的最长递增子序列的个数等于以7结尾的最长递增子序列的个数加上以6结尾的最长递增子序列的个数。

所以这个递归关系就很好找了，就是把所有小于当前值的可以构成最长递增子序列的值找出来，然后把它们对应的最长递增子序列的个数加起来即可。

我们回顾我们的O(n^2)的解法，我们可以用一个数组length来保存以特定元素结束的最大递增字符串的长度，比如length[i]表示以num[i]结尾的最长递增子序列的长度。
我们可以用count数组来保存以特定元素结束的最大递增字符串的长度，我们只需要注意到，对于 小于m的i和j来说，当length[i] + 1 == length[m] 和 length[j] + 1 == length[n]的时候，此时应该有count[m] = count[i] + count[j]。
如果说对于小于m的i，j，k来说，当length[i] + 1 == length[j] + 1 == length[k] + 1 = length[m]的时候，那么应该有count[m] = count[i] + count[j] + count[k]。

既然有了思路，我们写代码就简单多了，如下所示:

package com.mengzhidu.teach.algorithm.dp.demo.line;

/**
 * 获取最大递增子序列的个数
 */
public class LisDemo3 {
   
    public static void main(String[] args) {
   
        int[] num = {
   
1
2
3
4
5
6
7
8
9
10