子串和子序列
子串一定一定是连续的，而子序列是整个序列的一部分，可以使不连续的

数字三角形

每次从最后一层到(i, j)点的这条路径上的数字之和的最大值，从下到上分析比从上到下分析会更加容易一点

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510;

int dp[N][N];
int n;

int main ()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            cin >> dp[i][j];

    for (int i = n - 1; i >= 1; i -- )
        for (int j = 1; j <= n; j ++ )
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + dp[i][j];

    cout << dp[1][1] << endl;
    return 0;
}

最长上升子序列

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int dp[N]; // 转移数组
int a[N];  // 序列数组

int main ()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) // i从0或者1开始都可以，因为这题没有出现i-1这种下标
        cin >> a[i];          

    // dp[i] 表示以a[i]结尾的最长上升序列
    for (int i = 1; i <= n; i ++ )
    {
        dp[i] = 1; // 至少a[i]自己本身是一个上升的子序列，所以先初始化为1
        for (int j = 1; j < i; j ++ ) // 循环找可以以a[i]为结尾的上升子序列
            if (a[i] > a[j])
                dp[i] = max(dp[i], dp[j] + 1);
    }

    // 因为是求出以a[i]结尾的醉成上升子序列，所以不知道以哪个结尾的子序列是最长的
    // 所以要枚举所有的结尾，取其中的最大值
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        res = max(res, dp[i]);

    cout << res << endl;
    return 0;
}

最长公共子序列

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const int N = 1010;

int dp[N][N]; // dp[i][j]表示在第一个序列前i个序列中出现
              // 并且在第二个序列的前j个序列中出现的子序列的
int main ()
{
    int n, m;
    cin >> n >> m;
    string str1, str2;
    cin >> str1 >> str2;

    // i,j的下标都是从1开始是因为转移时有j-1,i-1,
    // 也就是说在str1有一个字符str2没有字符这样的特殊情况要特判
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= m; j ++ )
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            // 假设str1[i]!=str2[j],那就要在str1前i-1个序列str2前j个序列中找，
            // 或者str1前i个序列str2前j-1个序列中找，二者去最大值
            if (str1[i - 1] == str2[j - 1]) // 因为string是从0下标开始的所以要-1
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
        }

    cout << dp[n][m] << endl;
    return 0;
}