【算法笔记】深入理解dfs（两道dp题）

DFS过程的概述

一个一个节点的搜，如果是树状结构的话，先找到最左边那一条分支搜到最后一个节点，这个时候最后一个节点（假设是b）的数据会被更新（具体看题目的要求），然后返回到上一个节点(假设是a)（如果有两层dfs的话，需要画个分叉图辅助理解）。 此时a节点使用下层刚刚被更新过的数据(即b节点)来更新a节点的数据。更新完后如果a节点下方还有一个节点，那么就要继续往下搜索，继续把a节点的数据更新完全（也就是把a节点的分支都找完了）。那么当a节点的数据被完全更新完后，又会重复上面那个过程。也就是说我们可以把以a节点为根的子树看成一个新的节点（这样子方便理解）

从上面的分析可以看出，dfs会把更新后的数据存储起来，不管这个更新是完全更新还是部分更新。这个也很好理解，因为一次dfs只会对一个节点进行操作（而且是从下往上的过程）（这就说明一个节点可能要经过多次dfs才能把数据完全更新），也就是用一种很笨的方法（如果没有剪枝的话，和暴搜没区别）去更新数据和答案。

有依赖的背包问题

思路:在这一题里，我们需要更新每颗子树的最大价值，然后计算出包括根节点的树的最大价值。对于树的遍历，我们一般可以用dfs来遍历，因为dfs从最底层的节点开始往上遍历。

这里的f[ i ][ j ]的含义是考虑第i个物品为根节点的子树，且选上i，体积不超过j的最大价值。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
const int N = 110;
vector<int> g[N];
int v[N], w[N];
int f[N][N];
int n, m;

void dfs(int u)
{
    for(int i = v[u]; i <= m; i ++) f[u][i] = w[u];
    for(int i = 0; i < g[u].size(); i ++)
    {
        int y = g[u][i];
        dfs(y); //一直往下搜索树的节点，直到找到最底层的节点，然后执行状态转移方程，然后返回到上一个节点
        for(int j = m; j >= v[u]; j --)
            for(int k = 0; k <= j - v[u]; k ++)
            {
                f[u][j] = max(f[u][j], f[y][k] + f[u][j-k]);
            }
    }
}

int main()
{   
    int root;
    cin>>n>>m;
    for(int i = 1; i <= n; i ++)
    {
        int fa;
        cin>>v[i]>>w[i]>>fa;
        if(fa == -1) root = i;
        else 
            g[fa].push_back(i);
    }
    
    dfs(root);
    cout<<f[root][m];
}

导弹防御系统（线性dp）

思路：这一题好像没有什么好的办法，只能用dfs加剪枝，如果不剪枝的话肯定会TLE的，因为每个点有两种情况可选：加入到上升子序列或加入到下降子序列。那么综合以上来看的话，时间复杂度回到一个 n * 2 ^ n。

用两次dfs来搜索所有情况的组合。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 55;
int h[N];
int up[N], down[N];
int ans, n;

void dfs(int u, int su, int sd)
{
    if(su + sd >= ans) return; //剪枝，如果此时上升和下降序列的方案数大于等于ans那么直接返回
    
    if( u == n)
    {
        ans = min(ans, su + sd); //更新答案
        return;
    }

    //上升序列方案统计
    int k = 0;
    while( k < su && up[k] >= h[u]) k++;
    if( k < su)
    {
        int t = up[k];
        up[k] = h[u];
        dfs(u+1, su, sd);
        up[k] = t;
    }
    else
    {
        up[k] = h[u];
        dfs(u+1, su+1, sd);
    }
    
    //下降序列方案统计
    k = 0;
    while( k < sd && down[k] <= h[u]) k ++;
    if( k < sd)
    {
        int t = down[k];
        down[k] = h[u];
        dfs(u+1, su, sd);
        down[k] = t;
    }
    
    else
    {
        down[k] = h[u];
        dfs(u+1, su, sd+1);
    }

}

int main()
{
    while(cin>>n, n)
    {
        for(int i = 0; i < n; i ++) cin>>h[i];
        ans = n;    
        dfs(0, 0, 0);
        cout<<ans<<endl;
    }
}