动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程.

应用条件

  1.最优化问题
  2.重叠子问题
  3.子问题空间不能太大，DP通常情况下需要求解每一个子问题的最优解来组合得到原问题的最优解。

最优子结构 无后效性 子问题重叠

基本流程

1.刻画一个最优解的结构特征（状态设计）
2.递归的定义最优解的值（状态转移方程设计）
3.计算最优解的值，通常采用自底向上（递推）的方法（处理各种边界条件）

背包家族

01背包

你有一个容量固定为M的背包，以及N个物品。每一个物品具有一个固定的体积v和价值w。你需要在不超过背包容量的前提下最大化带走物品的价值。

状态转移方程
DP[i][j]=max(DP[i-1][j],DP[i-1][j-w[i]]+v[i])

第 i 个物品不在最优方案中（不取第 i 个物品），问题变成了考虑了前 i-1 个物品，总体积不超过 j 时的情况。当前，一种潜在的最优方案是前 i-1个物品，总体积不超过 j 时的最优方案；

第 i 个物品在最优方案中（取了第 i 个物品），问题变成了考虑了前 i-1 个物品，总体积不超过 j-v[i] 时的情况；当前，另一种潜在的最优方案是在考虑了前 i-1 个物品，总体积不超过 j-v[i] 时的最优方案的基础上再加上第 i 个物品，对应的收益是前 i-1 个物品，总体积不超过 j-v[i]时的最大收益 + 第 i 个物品的收益w[i]

根据题目会有一些非法状态，需要将其赋一个特殊值
(例如题目要求改为恰好装满容量为M的背包那么只有DP[0][0]为0,其他为负无穷)

记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 // 伪代码
 // 不记忆 O(2^(n-1))
 CUT（p,cnt）
 if(cnt==0)return 0;
    q=-∞;
    for  i  = 1 to cnt
q=max(q,p[i]+CUT(p,cnt-i))；
    p[cnt]=q;
 return p[cnt]; 
 // 记忆化搜索O(n^2)
 CUT（p,vis,cnt）
 if(cnt==0)return 0;
 if(vis[cnt])return p[cnt];
    q=-∞;
    for  i  = 1 to cnt
q=max(q,p[i]+CUT(p,cnt-i))；
    p[cnt]=q;
    vis[cnt]=true;   
 return p[cnt];

优化

dfs暴搜(MLE/TLE)
——> 优化

剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//O(nm) n个大小为m的数组
#include <bits/stdc++.h>
using namespace std;

int n, m, f[1001][1001], v[1001], w[1001];

int main() 
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
      scanf("%d%d", &v[i], &w[i]);
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i++)
    {
      for (int j = 0; j <= m; j++)
      {
         f[i][j]=f[i-1][j];
         if(j>=v[i])
         f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
      }
    }     
    printf("%d\n", f[n][m]);
}

滚动数组

两个大小为m的数组
在我们从小到大枚举 i 的过程中，前 i-2 行的值其实是不用记的（它们不会对后面产生影响），所以我们可以用两个大小为 m 的数组 f, g 来进行所有状态的计算，其中 f 用来记录 i - 1 行的值，g 用来计算第 i 行的值，当第 i 行计算完成的时候，g 就变成了新的 f，我们用它来计算新一行（第 i + 1）的 g 值。在执行过程中，f, g 两个数组周而复始、循环往复，这就是滚动数组的思想啦！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//O(m) 
#include <bits/stdc++.h>
using namespace std;

int n, m, f[1001], g[1001], v[1001], w[1001];

int main() 
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
      scanf("%d%d", &v[i], &w[i]);
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i++) 
    {
        memset(g, 0, sizeof(g));
        for (int j = 0; j <= m; j++)
        {
         if (j < v[i])
            g[j] = f[j];
         else
            g[j] = max(f[j], f[j - v[i]] + w[i]);
        memcpy(f, g, sizeof(g));
        }  
    }
    printf("%d\n", f[m]);    
}

一个大小为m的数组
假设现在 p 数组中记录的是第 i - 1 行的值，我们要计算第 i 行的值。
然后我们从右到左依次计算每个位置新的值（第 i 行的值）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//O(m)
#include <bits/stdc++.h>
using namespace std;

int n, m, p[1001], v[1001], w[1001];

int main() 
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
      scanf("%d%d", &v[i], &w[i]);
    }
    memset(p, 0, sizeof(p));
    for (int i = 1; i <= n; i++)
    {
      for (int j = m; j >= v[i]; j--)
      {
         p[j] = max(p[j], p[j - v[i]] + w[i]);
      }  
    }  
    printf("%d\n", p[m]);    
}

完全背包

完全背包和 01 背包的不同点是，在 01 背包问题中每种物品只能取一次，而在完全背包问题中物品没有取多少次的限制，想取多少次就取多少次。解决完全背包问题的思路和 01 背包问题的思路非常像。

第 i 种物品一个都没取，问题变成了考虑了前 i − 1 种物品，总体积为 j 时的情况；这一种情况是和 01 背包问题完全一样的；

第 i 种物品取了，问题变成了考虑了前 i 种物品，总体积为 j-v[i] 时的情况；当我们取了一个物品以后，第 i 种物品还可以继续取，所以我们仍然要继续考虑前 i 种物品的情况；
作为对比，在 01 背包问题中，如果第 i 个物品取了，由于每种物品最多取一次，问题会变成考虑了前 i - 1 种物品的情况

状态转移方程
DP[i][j]=max(DP[i-1][j],DP[i][j-v[i]]+w[i])

n个大小为m的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//O(nm)
#include <bits/stdc++.h>
using namespace std;

int n, m, f[1001][1001], v[1001], w[1001];

int main() 
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
      scanf("%d%d", &v[i], &w[i]);
    }
    memset(f, 128, sizeof(f)); //128表示负无穷
    f[0][0] = 0;               //保证恰好装满容量（设置合法状态）
    for (int i = 1; i <= n; i++)
    {
      for (int j = 0; j <= m; j++)  //j必须从小到大枚举
      {
         if (j < v[i])
            f[i][j] = f[i - 1][j];
         else
            f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
      }
    }   
    int ans = 0;
    for (int i = 0; i <= m; i++)//由于恰好条件，题目求最大，故进行循环筛选
        ans = max(ans, f[n][i]);
    printf("%d\n", ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//O(nm)
#include <bits/stdc++.h>
using namespace std;

int n, m, f[1001][1001], v[1001], w[1001];

int main() 
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i++)
        {
         for (int j = 0; j <= m; j++)
         {
            if (j < v[i])
                f[i][j] = f[i - 1][j];
            else
                f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
         }
        }
    printf("%d\n", f[n][m]);
}

一个大小为m的数组

第 i 个物品在最优方案中的情况下，用到了 f[i][j-v[i]] ，而 j-v[i] 一定小于 j，
第 i 个物品不在最优方案中的情况下，用到了 f[i - 1][j]

假设现在 p 数组中记录的是第 i - 1 行的值，我们要计算第 i 行的值。
和 01 背包问题相反，我们从左到右依次计算每个位置新的值（第 i 行的值）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h
using namespace std;

int n, m, p[1001], v[1001], w[1001];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    memset(p, 0, sizeof(p));
    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= m; j++)
                p[j] = max(p[j], p[j - v[i]] + w[i]);
    printf("%d\n", p[m]);    
}

多重背包

和 01 背包问题不一样的是，第 i 个物品不是只能取一次，而是可以取 l[i] 次

把它转换成一个 01 背包问题
一个可以取 l[i] 次的物品，等价于 l[i] 个只能取一次的物品

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//O(nml)
#include <bits/stdc++.h>
using namespace std;

int n, m, p[1001], v[1001], w[1001], l[1001];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &v[i], &w[i], &l[i]);
    memset(p, 0, sizeof(p));
    for (int i = 1; i <= n; i++)
        for (int k = 1; k <= l[i]; k++)
            for (int j = m; j >= v[i]; j--)
                p[j] = max(p[j], p[j - v[i]] + w[i]);
    printf("%d\n", p[m]);    
}

二进制拆分法

定理：令 t 为最大的 i 满足 2^(i+1)-1<=n ，我们从 1,2,4,…,2^t,n-2^(t+1)+1 中选一些数字相加（可以不选），可以得出任意 [0,n] 内的值.(每个数字只能用一次)

对于在 [0,2^(t+1)] 中的值，我们可以直接从 1,2,4,…,2^t 中选一些数字相加得到；
对于在 [2^(t+1),n] 内的值，我们取 n-2^(t+1)+1 后，
令 [2^(t+1),n] 同减去 n-2^(t+1)+1 ，得 [2^(t+2)-n-1,2^(t+1)] ,
则剩下的数字在 [2^(t+2)-n-1,2^(t+1)] 内，可以从 1,2,4,…,2^t 中选一些数字相加得到.

举个例子，当 l[i]=8 时，我们会把第 i 个物品拆成 4 个物品：
取 1 次第 i 种物品的打包；
取 2 次第 i 种物品的打包；
取 4 次第 i 种物品的打包；
取 1 次第 i 种物品的打包.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// O(nmlog l)
#include <bits/stdc++.h>
using namespace std;

int n, m, p[2001], v[2001], w[2001], l[2001];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &v[i], &w[i], &l[i]);
    memset(p, 0, sizeof(p));
    for (int i = 1; i <= n; i++) 
    {
        int res = l[i];
        for (int k = 1; k <= res; res -= k, k *= 2)
            for (int j = m; j >= v[i] * k; j--)
                p[j] = max(p[j], p[j - v[i] * k] + w[i] * k);
        for (int j = m; j >= v[i] * res; j--)
            p[j] = max(p[j], p[j - v[i] * res] + w[i] * res);
    }
    printf("%d\n", p[m]);    
}

分组背包

二维背包

LIS

最长上升子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 朴素做法 O(n^2)
#include<bits/stdc++.h>
using namespace std;

int const N=5e3+10;
int n,a[N],f[N],pre[N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;++i)
    {
        f[i]=1;
        for(int j=1;j<i;++j)
        {
            if(a[j]<a[i])  
            {
                if(f[j]+1>f[i])  pre[i]=j;  //记录更新元素的前一个元素序号
                f[i]=max(f[i],f[j]+1);
            }
        }
    }
    int ans=-1,ind=0;
    for(int i=1;i<=n;++i)
    {
        if(f[i]>ans) ind=i; //记录最长子序列最后一个元素的序号
        ans=max(ans,f[i]); //记录最长子序列元素个数
    }
    cout<<ans<<endl;  //输出序列长度
//递归函数
    function<void(int x)>dfs=[&](int x)  
    {
        if(pre[x]=-1)
        {
            cout<<a[x]<<" ";
            return;  
        }
        dfs(pre[x]);
        cout<<a[x]<<" ";
    };

    dfs(ind);
    return 0;
}

动态规划具有 判断性继承思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// 记忆化搜索
#include<bits/stdc++.h>
using namespace std;

int const N=5e3+10;
int n,a[N],dp[N];

int dfs(int i)
{
    if(dp[i]!=-1) return dp[i];
    int ans=1;
    for(int j=1;j<i;++j)
    {
        if(a[j]<a[i])  ans=max(ans,dfs(j)+1);
    }
}
int main()
{
    memset(dp,-1,sizeof(dp));
    cin>>n;
    for(int k=1;k<=n;++k)
    {
        cin>>a[k];
    }
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        ans=max(ans,dfs(i));
    }
    cout<<ans<<endl;
}

```C++
// O( n*logn)
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x7fffffff;     //无穷大
const int N = 1e5+10;
long long a[N],f[N];    //f[i]记录长度为i的上升子序列的最小末数值

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        f[i]=INF;   //  f[i]设为无穷大，便于后续小的数替换
    }
    f[1]=a[1];
    
    int len=1;
    for(int i=2;i<=n;i++)   //二分查找，降低时间复杂度
    {
        int l=0,r=len,mid;
        if(a[i]>f[len]) f[++len]=a[i];
        else
        {
            while(l<r)
            {
                mid=(l+r)/2;
                if(f[mid]>a[i]) r=mid;
                else    l=mid+1;
            }
            f[l]=min(a[i],f[l]);
        }
    }
    cout<<len;
    return 0;
}

LCS

最长公共子序列


此题用n方时间复杂度会被10的5次方卡死
要考虑 nlogn 做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// O(n*m)
#include <bits/stdc++.h>
using namespace std;
const int N =1e2+10;
int dp[N][N],a[N],b[N];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<m;i++)
    {
        cin>>b[i];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(a[i]==b[j])  dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
        }
    }
    cout<<dp[n-1][m-1];     //输出最长公共子序列长度
    return 0;
}

将LCS转化为LIS问题，降低时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// O(n*logn)
#include <bits/stdc++.h>
using namespace std;
const int N =1e5+10;
int m[N],dp[N],a[N],b[N];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        m[a[i]]=i;    //标志a序列数字在a中位置
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
        dp[i]=0x7fffffff;
    }
    int len=0;
    dp[0]=0;
    for(int i=1;i<=n;i++)
    {
        int l=0,r=len,mid;
        if(m[b[i]]>dp[len]) //b中第i个数在a中位置
        {
            dp[++len]=m[b[i]];
        }
        else
        {
            while(l<r)
            {
                mid=(l+r)/2;
                if(dp[mid]>m[b[i]])
                {
                    r=mid;
                }
                else
                {
                    l=mid+1;
                }
            }
            dp[l]=min(m[b[i]],dp[l]);
        }
    }
    cout<<len;
    return 0;
}

区间dp

石子合并

铺垫————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//石子合并，一排石子，找两两合并的minn
//记忆化部分代码用注释表示
#include <bits/stdc++.h>
using namespace std;
int n,a[501],s[501];
//int f[501][501]; 表示合并第i到j堆石子的价值

int solve(int l,int r)
{
    //if(f[l][r]!=-1)    return f[l][r];
    if(l==r)    return 0;
    //↓ if(l==r)    return f[l][r]=0;
    int ans=1<<30;
    for(int m=l;m<r;m++)    //枚举断点(分界线)
    {
        ans=min(ans,solve(l,m)+solve(m+1,r));   
        //递归(重复运算，花费时间,需要记忆化搜索)
    }
    return ans+s[r]-s[l-1]; //加上最后一次合并的价值
    //↓ return f[l][r]=ans+s[r]-s[l-1];
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        s[i]=s[i-1]+a[i];   //前缀和
    }
    //memset(f,255,sizeof(f)); 初始化
    printf("%d\n",solve(1,n));
}

板子————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
const int N =1e3+10;

void solve()
{
    int n;
    cin>>n;
    vector<int> num(n*2+1),sum(n*2+1);
    for(int i=1;i<=n;i++)
    {
        cin>>num[i];
        num[i+n]=num[i];          //复制成环
    }
    //dp[i][j]  合并从i到j的石子
    vector<vector<int>> minn(n*2+1,vector<int>(n*2+1,0x3f3f3f)),
                        maxx(n*2+1,vector<int>(n*2+1));
    for(int i=1;i<=n*2;i++)
    {
        sum[i]=sum[i-1]+num[i];   //前缀和
        minn[i][i]=0;
    }
    for(int len=1;len<=n;len++)    //合并区间长度
    {
        for(int i=1;i+len<=2*n;i++) //当前区间起点
        {
            for(int k=i;k<i+len;k++)  //当前区间断点
            {
                int j=i+len;
                minn[i][j]=min(minn[i][j],minn[i][k]+minn[k+1][j]+sum[j]-sum[i-1]);
                maxx[i][j]=max(maxx[i][j],maxx[i][k]+maxx[k+1][j]+sum[j]-sum[i-1]);
            }
        }
    }
    int ans=0x3f3f3f3f;     //无穷大
    for(int i=1;i<=n;i++)
    {
        ans=min(ans,minn[i][i+n-1]);
    }
    cout<<ans<<endl;
    ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,maxx[i][i+n-1]);
    }
    cout<<ans<<endl;
    return;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t=1;
//  cin>>t;
    while(t--)
    {
        solve();
    }

    return 0;
}

树形dp


有点权, 记录点e[], 找根in[], dp[][0/1]进行选择

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
const int N =1e3+10;

void solve()
{
    int n;
    cin>>n;
    vector<int> num(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>num[i];    //每个点的价值
    }
    vector<vector<int>> e(n+1);
    vector<int> in(n+1);
    for(int i=1;i<n;i++)
    {
        int v,u;        //v下属,u直接上司
        cin>>v>>u;
        e[u].push_back(v);
        in[v]++;
    }

    vector<vector<int>> dp(n+1,vector<int>(2));
    vector<int> vis(n+1);

    for(int i=1;i<=n;i++)
    {
        dp[i][1]=num[i];        //选中则得到价值
    }

    auto dfs=[&](auto dfs,int u)->void
    {
        if(vis[u])  return;
        vis[u]=1;
        for(auto v:e[u])
        {
            dfs(dfs,v);
            dp[u][0]+=max(dp[v][1],dp[v][0]);  //dp[i][0]表示不参与，dp[i][1]表示参与
            dp[u][1]+=dp[v][0];
        }
    };

    for(int i=1;i<=n;i++)
    {
        if(in[i]==0)
        {
            dfs(dfs,i); //从根开始遍历
            cout<<max(dp[i][0],dp[i][1]);
        }
    }
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t=1;
//    cin>>t;
    while(t--)
    {
        solve();
    }

    return 0;
}

二叉苹果树
有边权，链表记录边e[]，记录节点以下边数目sz[]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
const int N =1e2+10;
int n,q,f[N][N];    //f[i][j]表示i为根的树保留j条树枝的最大值

struct edge
{
    int w,to,nxt;
}e[N<<1];   //双向边
int tot,head[N];

inline void add(int u,int v,int w)
{
    e[tot]={w,v,head[u]};   //nxt接上一节点序号(父节点序号)
    head[u]=tot++;
}

int sz[N];
void dfs(int u,int fa)
{
    for(int i=head[u];~i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==fa)   continue;
        dfs(v,u);
        sz[u]+=sz[v]+1; //u节点的树枝数目
        for(int j=min(sz[u],q);j;--j)  //保留树枝数目
        {
            for(int k=min(sz[v],j-1);k>=0;--k)
            {
                f[u][j]=max(f[u][j],f[u][j-k-1]+f[v][k]+e[i].w);
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    memset(head,-1,sizeof(head));
    cin>>n>>q;
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1,-1);
    cout<<f[1][q]<<endl;
    return 0;
}

状压dp

将状态压缩为整数来达到优化转移的目的