如何在 C 语言中利用动态规划求解 LIS?

在 C 语言中，我们可以使用动态规划（Dynamic Programming）来求解最长上升子序列问题。这里是一个简单的步骤：

1. 定义一个数组 `dp`，其长度与输入数组相同，所有元素初始化为 1。这是因为每一个单个的元素本身就是它的最长上升子序列。

int dp[n];

2. 遍历输入数组 `arr`，从第二个元素开始（假设索引为 i），比较当前元素 `arr[i]` 和 `arr[j]`（其中 j 是已处理过的元素）。如果 `arr[i] > arr[j]` 并且 `dp[i] < dp[j] + 1`，说明找到了一个新的子序列，更新 `dp[i]` 为 `dp[j] + 1`。

for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
            dp[i] = dp[j] + 1;
        }
    }
}

3. 最终，数组 `dp` 中的最大值即为最长上升子序列的长度。

int max_len = *max_element(dp, dp+n);

4. 欲找出具体的最长上升子序列，可以在遍历过程中记录下哪些元素满足了 `dp[i] = dp[j] + 1` 的条件，并将其添加到结果序列中。

vector<int> lis(max_len);
// 使用回溯法或者类似的方法将 dp 中找到的最长上升子序列填充到 lis 数组中

这就是在 C 语言中利用动态规划求解最长上升子序列的基本思路。