集合划分原则：不重不漏，找最后一个不同点

整数划分问题

选择( 背包)

区间dp

区间dp循环的时候可以先循环区间的长度

例题 密码脱落

https://www.acwing.com/problem/content/1224/

增加的就是原字符中中不是回文序列的字符的数量

一. 状态表示

l,r之间的回文子序列的长度

二. 状态划分

1. L,R都在集合里
   f[l+1,r-1] + 2
2. L在集合里
   f[l,r-1]
3. R在集合里
   f[l+1,r]
4. L,R都不在集合里
   f[l+1,r-1]

区间dp循环的时候可以先循环区间的长度

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int f[maxn][maxn];
#define INF 0x3f3f3f3f
int main()
{
    string ss ;
    cin >> ss ;
    //memset(f,-INF, sizeof(f));
    f[0][0] = 0;
    for(int len = 1; len <= ss.length() ; ++len) {
        for(int l = 0; l < ss.length(); l++)  {
            int r = l + len -1;
            if(len == 1) {
                f[l][r] = 1;
                continue;
            }
            if(ss[l] == ss[r]) 
                f[l][r] = f[l + 1][ r - 1] + 2;
            f[l][r] = max(f[l][r],f[l][r - 1]);
            f[l][r] = max(f[l][r], f[l + 1][r]);
            // cout<<f[l][r]<<endl;
        }
    }
    cout<<ss.length() - f[0][ss.length() - 1] <<endl;
    return 0;
}

树形dp

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
#define INF 0x3f3f3f3f
typedef long long ll;
ll f[maxn];
ll a[maxn];
vector<ll> g[maxn];

void dfs(int u,int fa){
    f[u] = a[u];
    for(auto v:g[u]){
        // cout<<v<<endl;
        if(v == fa ) continue;
        dfs(v,u); 
        f[u] = max(f[u],f[u] + f[v]);
        // cout<<f[u]<< " "<<f[v]<<endl;
    }
}

int main()
{
    int n;
    cin>>n;
    for(int i = 1;i <= n; ++i)
        cin>>a[i];
    int u,v;
    // memset(f,-INF,sizeof(f));
    for(int i = 1;i <= n - 1; ++i )  {
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    ll ans = -INF;
    for(int i = 1;i <= n; i++)
        ans = max(ans,f[i]);
    cout<<ans<<endl;
    return 0;
}