动态规划太难？这5个经典模型帮你快速入门，60名一等奖学员都在用

// 01背包 - 一维优化
for (int i = 1; i <= n; i++)
    for (int j = V; j >= w[i]; j--)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

// O(n²)写法
for (int i = 1; i <= n; i++) {
    dp[i] = 1;
    for (int j = 1; j < i; j++)
        if (a[j] < a[i])
            dp[i] = max(dp[i], dp[j] + 1);
}
// 答案是max(dp[1..n])

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (a[i] == b[j])
            dp[i][j] = dp[i-1][j-1] + 1;
        else
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

for (int len = 2; len <= n; len++)           // 区间长度
    for (int l = 1; l + len - 1 <= n; l++) { // 区间左端点
        int r = l + len - 1;                  // 区间右端点
        for (int k = l; k < r; k++)           // 分割点
            dp[l][r] = max(dp[l][r], dp[l][k] + dp[k+1][r] + w[l][r]);
    }

void dfs(int u, int fa) {
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
        // 状态转移，比如选或不选
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}