我从这里重现我的算法，其中解释了其逻辑：
dp[i, j] = same as before num[i] = how many subsequences that end with i (element, not index this time) have a certain lengthfor i = 1 to n do dp[i, 1] = 1for p = 2 to k do // for each length this time num = {0} for i = 2 to n do // note: dp[1, p > 1] = 0 // how many that end with the previous element // have length p - 1 num[ array[i - 1] ] += dp[i - 1, p - 1] *1* // append the current element to all those smaller than it // that end an increasing subsequence of length p - 1, // creating an increasing subsequence of length p for j = 1 to array[i] - 1 do *2* dp[i, p] += num[j]您可以使用段树或二进制索引树进行优化
*1*和
*2*使用。这些将用于有效处理
num阵列上的以下操作：
- 鉴于
(x, v)
加v
至num[x]
（相关*1*
）; - 给定
x
，求和num[1] + num[2] + ... + num[x]
（与有关*2*
）。
对于这两种数据结构来说，这都是微不足道的问题。
注意： 这将具有复杂性
O(n*k*log S)，这
S是数组中值的上限。这可能足够，也可能不够。为此
O(n*k*logn)，您需要在运行上述算法之前规范化数组的值。规范化意味着将所有数组值转换为小于或等于的值
n。所以这：
5235 223 1000 40 40
成为：
4 2 3 1 1
这可以通过排序（保留原始索引）来完成。
