最简单的动态规划

最长连续子列和

dp[i]表示以i为结尾的连续子列和的最大值
初始化第一个元素的最大连续子列和就是自己
从第2个数开始遍历余下的数，若到之前一个数为止的最大子列和dp[i-1]加上当前数构成的新的最大连续子列和较当前数更大，则子列可以继续延长更新为dp[i]，否则当前数更大，以i为结尾的最大连续子列和是自身

alt

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 10010;

int A[maxn], dp[maxn];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &A[i]);
	}
	// 边界，第一个数的结果就是自身，以第2个数为结尾的最大连续子列和可以通过dp[0]推得，后一个数由前一个数的dp值推得，如此整个dp就可以推出来
	dp[0] = A[0];
	for (int i = 1; i < n; i++) {
		// 状态转移方程，如果加上当前数后更大则更新dp数组，否则就是自身 
		dp[i] = max(A[i], dp[i - 1] + A[i]);
	}
	// dp[i]存放以A[i]结尾的连续序列的最大和（不关心从哪里开始），需要遍历dp数组得到最大值才是结果 
	int k = 0;
	for (int i = 1; i < n; i++) {
		if (dp[i] > dp[k]) {
			k = i;
		}
	}
	printf("%d\n", dp[k]);
	return 0;
}

//5
//-2 11 -4 13 -5 -2

最长不下降子列和

dp[i]表示以i结尾的最大上升序列和最大值
初始化，每个元素的最大上升序列和值就是自身，这是每次一进入内层循环所做的
状态转移，从第0个元素一直扫描到第i个元素的前一个元素a[j]（上升序列可以不连续），判断是否比当前元素小，若是，则可以构成不下降子列，与当前已有的以i为结尾的最大不下降子序列和dp[i]结果比较，选择与dp[i-1]+a[i]的较大值，dp[i-1]用到了之前的结果（不一定dp[i-1]+a[i]一定更大可直接更新，例如1 7 3 5 9，扫描到9时，下标为2的元素3的确比9小可以构成上升序列一部分，dp[2]+a[4]=4+9=13，但之前已有1 7 9这个组合，dp[4]已更新为17，故选择之前较大的那个连续子序列而不是1 3 9这个组合）；若不是，极端点，前面数都比它大，不下降子序列只能是它自身

alt

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1001;

int dp[N]; // dp[i]表示以A[i]结尾的最长上升子序列的长度，不要求连续，因此a[i]前面数每个数都需要判断

// 最大上升子序列和，最长的上升子序列和不一定是最大的
int main() {
    int n, A[N];
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &A[i]);
        }
        int ans = -1;
        for (int i = 0; i < n; i++) {
            dp[i] = A[i]; // 边界初始条件，每个元素自成一个子序列 
            for (int j = 0; j < i; j++) {
                if (A[j] < A[i]) { // 如果A[j] < A[i]，则A[i]可以接在A[j]后面构成一个更长的上升子序列 
                    dp[i] = max(dp[i], dp[j] + A[i]); // 更新dp[i]为更大的值 
                }
            }
            ans = max(ans, dp[i]); // 更新ans为最大的长度 
        }
        printf("%d\n", ans);
    }
    return 0;
}

两个序列最长公共长度

dp[i][j]代表字符串s1的到i个字符为止与s2的第j个字符为止已匹配的字符数量
第0行与第0列都是0，因为s1 0字符和s2 0字符都无法与对方匹配，都是0
若当前字符匹配，则必定在双方到i-1个字符为止的已匹配的字符数+1，若不匹配，则一定是s1的到前一个字母为止与s2当前字符位置已匹配的字符数或s1当前字符为止与s2的前一个字符为止已匹配的字符数的最大值，至少之前至少有字符匹配过（这些dp[i][j]提前算过了）

alt

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

#define N 1001
int dp[N][N]; // dp[i][j]代表字符串s1与s2已匹配的字符数

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    int n = s1.size();
    int m = s2.size();
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
                continue;
            }
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    printf("%d\n", dp[n][m]);
    return 0;
}