最长上升子序列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数组，找到其中的最大值，即为最长上升子序列的长度。

相关问题

最长递增子序列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`，都需要遍历`0~i-1`的所有元素，如果`nums[i]`大于`nums[j]`，则可以将`dp[i]`更新为`dp[j]+1`，表示在以`nums[j]`为结尾的最长递增子序列后面加上`nums[i]`可以得到一个更长的递增子序列。最后，遍历`dp`数组，找到其中的最大值即为所求的最长递增子序列的长度。

c++算法写最长公共子序列

最长公共子序列问题是一个经典的动态规划问题。假设有两个序列 $A=a_1,a_2,...,a_m$ 和 $B=b_1,b_2,...,b_n$，求它们的最长公共子序列（LCS）。

定义 $c[i][j]$ 为序列 $A$ 的前 $i$ 个元素和序列 $B$ 的前 $j$ 个元素的 LCS 的长度。则有以下递推公式：

$c[i][j]=\begin{cases}
0, & i=0 \text{ or } j=0 \\
c[i-1][j-1]+1, & a_i=b_j \\
\max(c[i-1][j],c[i][j-1]), & a_i \neq b_j
\end{cases}$

其中 $c[i-1][j-1]+1$ 表示如果 $a_i=b_j$，那么 $a_i$ 和 $b_j$ 必然是 LCS 的一部分，所以 LCS 长度加 $1$；$\max(c[i-1][j],c[i][j-1])$ 表示如果 $a_i \neq b_j$，则 $a_i$ 和 $b_j$ 不可能同时出现在 LCS 中，所以 LCS 的长度就是序列 $A$ 的前 $i-1$ 个元素和序列 $B$ 的前 $j$ 个元素的 LCS 的长度，以及序列 $A$ 的前 $i$ 个元素和序列 $B$ 的前 $j-1$ 个元素的 LCS 的长度的最大值。

最终的 LCS 长度即为 $c[m][n]$。而要得到 LCS 的具体内容，可以倒着遍历 $c$ 数组，按照递推公式的规则向左上方移动，并记录下相同的字符即可。

下面是 C 语言代码实现：

#include <stdio.h>
#include <string.h>

#define MAXLEN 100

int max(int a, int b) {
    return a > b ? a : b;
}

void LCS(char* A, char* B, int m, int n, int c[][MAXLEN]) {
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (A[i - 1] == B[j - 1]) {
                c[i][j] = c[i - 1][j - 1] + 1;
            } else {
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
            }
        }
    }
}

void printLCS(char* A, int m, int n, int c[][MAXLEN]) {
    char lcs[MAXLEN];
    int len = 0;

    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (A[i - 1] == A[j - 1]) {
            lcs[len++] = A[i - 1];
            i--;
            j--;
        } else if (c[i - 1][j] > c[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    printf("LCS: ");
    for (int k = len - 1; k >= 0; k--) {
        printf("%c", lcs[k]);
    }
    printf("\n");
}

int main() {
    char A[] = "ABCBDAB";
    char B[] = "BDCABA";

    int m = strlen(A);
    int n = strlen(B);

    int c[MAXLEN][MAXLEN] = {0};
    LCS(A, B, m, n, c);

    printf("LCS length: %d\n", c[m][n]);
    printLCS(A, m, n, c);

    return 0;
}

输出结果为：

LCS length: 4
LCS: BCBA