最长上升子序列c++递推公式

最长上升子序列（Longest Increasing Subsequence，简称LIS）是指在一个无序的序列中，找到一个尽可能长的子序列使得这个子序列中的元素是递增的。下面是C++的递推公式：

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) {
        return 0;
    }
    vector<int> dp(n, 1);
    int res = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        res = max(res, dp[i]);
    }
    return res;
}

其中，dp[i]表示以nums[i]为结尾的最长上升子序列的长度。在遍历到nums[i]时，我们需要遍历nums[0]到nums[i-1]，找到所有小于nums[i]的数nums[j]，然后更新dp[i]为max(dp[i], dp[j]+1)。最后，我们遍历dp数组，找到其中的最大值，即为最长上升子序列的长度。