最长上升子序列方案数

---

📘 题目描述

给定一个由 $n$ 个正整数组成的序列 $a[1\ldots n]$（$1 \le n \le 5000$，$a_i \le 10^9$），请你：

• 求出 LIS 的方案数

---

💡 解题思路

LIS 的长度通过经典 DP 求解即可，这里重点讨论如何统计方案数。

---

🔢 状态定义

• f[i]：以第 i 个元素结尾的 LIS 的长度
• g[i]：以第 i 个元素结尾的 LIS 的方案数

---

🔁 状态转移

遍历每对 j < i，如果 a[j] < a[i]，说明可以连接成上升子序列：

• 如果 f[j] + 1 > f[i]：
  找到更长的子序列
  👉 更新 f[i] = f[j] + 1，g[i] = g[j]（继承方案数）

• 如果 f[j] + 1 == f[i]：
  找到一条等长的路径
  👉 累加方案数：g[i] += g[j]

🟡 初始化：

每个位置自身都是一个长度为 $1$ 的 LIS：

f[i] = 1, g[i] = 1;

✅ 统计答案

最终的最长长度为：int ans = max(f[1……n])。

总方案数为所有 f[i] == ans 的 g[i] 之和：

for (int i = 1; i <= n; ++i) 
{
    if (f[i] == ans) sum += g[i];
}

⏱️复杂度分析

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

✅ 代码实现

for (int i = 1; i <= n; i++)
{
    f[i] = 1, g[i] = 1; // 初始化方案数也为 1
    for (int j = 1; j < i; j++)
    {
        if (a[j] < a[i])
        {
            if (f[j] + 1 > f[i])
            {
                f[i] = f[j] + 1;
                g[i] = g[j];
            }
            else if (f[j] + 1 == f[i])
            {
                g[i] += g[j];
            }
        }
    }
    ans = max(ans, f[i]);
}
for (int i = 1; i <= n; i++)
{
    if (f[i] == ans)
    {
        sum += g[i];
    }
}