3562. 折扣价交易股票的最大利润（树上背包学习）

思路讲解

【树上背包【力扣周赛 451】】 https://www.bilibili.com/video/BV1o1jgzJE51/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37

这个视频讲树上背包问题讲的非常透彻，非常好。

这个第一个遍历边就不多说了，第二个循环倒过来是因为滚动数组优化，第三个必须正过来，你可以倒过来试一试，当数据中含有这个需要0元，但是价值不为0的物品时就会出错，这是因为倒过来遍历可能取了这个物品两次，正过来遍历的时候是空的，那么就不存在这个问题了。

      
auto dfs=[&](this auto &&self,int u,int p)->void{
    
    for(auto v:g[u]){
        if(v==p) continue;
        self(v,u);
    }
    // memo是暂时不考虑当前节点u而定的
    vector<array<int,3> > memo(budget+5,{0,0,0});
    
     for(auto &v:g[u]){
        for(int i=budget;i>=0;--i){
            for(int j=0;j<=i;++j){  // 必须要正过来循环
                memo[i][1]=max(memo[i][1],memo[i-j][1]+dp[1][v][j]);
                memo[i][2]=max(memo[i][2],memo[i-j][2]+dp[2][v][j]);
            }
        }
    }
    for(int i=budget;i>=0;--i){
        for(int j=1;j<=2;++j){
            int cost=present[u-1]/j;
            dp[j][u][i]=max(dp[j][u][i],memo[i][1]);
            if(i>=cost){
                dp[j][u][i]=max(dp[j][u][i],future[u-1]-cost+memo[i-cost][2]);
            }
        }
    }
};

AC代码

源代码

class Solution {
public:
    int maxProfit(int n, vector<int>& present, vector<int>& future, vector<vector<int>>& hierarchy, int budget) {
        int dp[3][170][170];
        for(int i=1;i<=2;++i){      // init
            for(int j=0;j<=n+5;++j){
                for(int k=0;k<=budget+5;++k){
                    dp[i][j][k]=0;
                }
            }
        }
        vector<vector<int> > g(n+5);
        for(auto &t:hierarchy){
            g[t[0]].push_back(t[1]);
        }
        // ism==1是父亲没买，ism==2是父亲买了
        auto dfs=[&](this auto &&self,int u,int p)->void{
            
            for(auto v:g[u]){
                if(v==p) continue;
                self(v,u);
            }
            // memo是暂时不考虑当前节点u而定的
            vector<array<int,3> > memo(budget+5,{0,0,0});
            
             for(auto &v:g[u]){
                for(int i=budget;i>=0;--i){
                    for(int j=0;j<=i;++j){  // 必须要正过来循环
                        memo[i][1]=max(memo[i][1],memo[i-j][1]+dp[1][v][j]);
                        memo[i][2]=max(memo[i][2],memo[i-j][2]+dp[2][v][j]);
                    }
                }
            }
            for(int i=budget;i>=0;--i){
                for(int j=1;j<=2;++j){
                    int cost=present[u-1]/j;
                    dp[j][u][i]=max(dp[j][u][i],memo[i][1]);
                    if(i>=cost){
                        dp[j][u][i]=max(dp[j][u][i],future[u-1]-cost+memo[i-cost][2]);
                    }
                }
            }
        };
        dfs(1,1);
        int ans=0;
        for(int i=budget;i>=0;--i){
            ans=max({ans,dp[1][1][i]});
        }
        return ans;
    }
};

心路历程（WA，TLE，MLE……）