动态规划（子问题最优解递推）

特点

  • 问题可以划分为若干个子问题，从最小的子问题开始向上递推，最终解决总问题

例题

1、树形 dp（基础版）

题目描述

n 个结点的无权无向图，结点存权重，有 n-1 条边，边相连结点不能同时选择，求最大权重和

代码逻辑

  • 边数比结点数少 1，构成树，无向图可以用任意结点作根结点
  • 当下结点是否被选择这一信息必须保留，这是一个二维 dp 问题
  • dpi0表示以 i 为根且 i 不选的最优结果，dpi1表示以 i 为根且 i 选的最优结果，树划分为若干个子树
  • 对每一个结点取它的最优解用来更新它父节点的结果，最终得到根结点的最优结果

核心代码

1
2
3
4
5
6
7
8
9
10
11
void dfs(int cur,int fath)
   {
       for(int ver : edge[cur])
       {
           if(ver==fath)
               continue;
           dfs(ver,cur); //从子问题得到总问题的解，先要解出子问题
           dp[cur][0] += max(dp[ver][0],dp[ver][1]);
           dp[cur][1] += dp[ver][0];
       }
   }

2、树形 dp（拓展版）

题目描述

n 个结点的无权有向图，结点存代价，边相连结点可以互相监视，求全部结点都被监视的最小代价

代码逻辑

  • 有向，所以要先找到总根，然后划分为子树，解决子问题再递推到总问题
  • 二维 dp 问题，以 i 为根的子问题：如果 i 被选择，那么子结点选不选都可以让这棵树全部结点都被监视，如果 i 不被选择且要求这棵树不借助外来监视就可以被完全监视，那么子结点至少选一个，如果 i 不被选择且必须借助外来监视，那么子结点可以不选
  • 0 表示选择根结点，1 表示不选择根节点但是整棵树被监视，2 表示不选择根结点，除了根节点之外整棵树被监视
  • 根结点不选而且整棵树必须不借助外来监视就被完全监视，子树只能是 0 或者 1 状态，取最小值加到当下树即可，但是子树至少有一个是 0 状态，才能保证当下树是 0 状态，为了去掉子树的最小值都在 1 状态取的情况，求出每一个子树从最小值对应的状态到 0 状态的最小偏移量，当下树的结果加上这个偏移量
  • 最后的答案从 dproot,0和 dproot,1中取一个最小值，不能取 dp~root,2

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(int cur)
   {
       for(int ver : edge[cur])
       {
           dfs(ver);  //从子问题得到总问题的解，先要解出子问题
           //cur被选，子结点任意
           dp[cur][0] += min(dp[ver][0],dp[ver][1],dp[ver][2]);
           //cur不选但整棵树被监视，子结点不允许借助外来监视
           dp[cur][1] += min(dp[ver][0],dp[ver][1]);
	//对于状态1，对于每一个子结点都不要求必须选择，但是至少一个子结点需要被选择，下面排除一个子结点都不选的情况
           dt = min(dt,dp[ver][0] - min(dp[ver][0],dp[ver][1]) );
           //cur不选且必须借助外来监视，子结点不可选择，且子结点不可借助外来监视
           dp[cur][2] += dp[ver][1];
       }
       //如果最小偏移量为0，那么说明已经至少选择了一个子结点，那么dp[cur][1]需要加的量也就是0
       dp[cur][1] += dt;
   }

3、区间 dp

问题描述

n 块石头重量分别是 wi，合并两堆石头的代价是两堆石头的总重量和，只能合并相邻两堆石堆，求所有石头被合并为一堆石头最小代价

代码逻辑

  • 由于只能合并相邻两堆石堆，把问题划分为区间最值，dpij表示 i 到 j 之间的石头被合成一堆的最小代价，i 到 j 之间的石头被分作两堆的方式很多，子问题划分的时候只有一件事是确定的，那就是子问题的石堆的长度小于总问题，比如 1-5 合并成 1 堆，可以先把 1-3 合并为 1 堆，4-5 合并成 1 堆，然后再把这两堆合并，也可以 1-2 合并，3-5 合并，然后这两堆合并，但是无论无何，总问题 1 堆长 5，子问题 1 堆的长度必然小于 5，根据堆的长度做递推。长度确定后，遍历起点 i，终点 j 就固定为 i+len-1，此时考虑 dpij，它可以由很多种不同的方式转移过来，选一个结果最优的即可。

核心代码_预处理

1
2
3
4
5
6
7
8
9
10
//dp预处理
memset(dp,inf,sizeof(dp))
   for(int i=1;i<=n;i++)
       dp[i][i] = 0;
//前缀和预处理
for(int i=1;i<=n;i++)
   {
       cin>>w[i];
       pre[i] = pre[i-1] + w[i];
   }

核心代码_递推

1
2
3
4
5
6
7
8
9
10
for(int len=2;len<=n;len++)
   {
       for(int i=1;i<=n-len+1;i++)
       {
           j = i + len - 1;
           for(int k=i;k<j;k++)  //遍历所有可能转移到当下结果的子结果，取最小的
               dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1] );

       }
   }