骨骼虚拟上门

请问第二轮问2是求某个node下面tree的大小吗? 问3的validate和问1有什么区别啊?

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

第一题原题可以O(k)， 但followup里加了multiplier 只能O(k^2)了吧？

有没有好心人能贴一下第一题follow up  dfs + memo的代码？在好多地方都看到这个题但是自己一直没想明白

第一题的follow-up

1.     int n, k;
   
2.     vector<int> arr, multiplier;
   
3.    
   
4.     // dp[l][r] stands for the max result we can get
   
5.     // if we take l elements from left, and r elements from right
   
6.     vector<vector<int>> dp;
   
7.    
   
8.     // the max result we can get
   
9.     // if we take l elements from left, and r elements from right
   
10.     int dfs(int l, int r)
    
11.     {
    
12.         if(l == 0 && r == 0)
    
13.             return 0;
    
14.         int &v = dp[l][r];
    
15.         if(v > INT_MIN)
    
16.             return v;
    
17.         // consider the last element we choose
    
18.         // if the last element is chosen from left, it should be the (l-1)-th element in arr
    
19.         // if the last element is chosen from right, it should be the (n-r)-th element in arr
    
20.         // the multiplier will always be (l+r-1)-th element in multipliers
    
21.         if(l > 0)
    
22.             v = max(v, dfs(l-1, r) + arr[l-1]*multiplier[l+r-1]);
    
23.         if(r > 0)
    
24.             v = max(v, dfs(l, r-1) + arr[n-r]*multiplier[l+r-1]);
    
25.         return v;
    
26.     }
    
27. 
    
28.     int main() {
    
29.         cin >> n >> k;
    
30.         arr = vector<int>(n), multiplier = vector<int>(k);
    
31.         for(int i = 0; i < n; ++i)
    
32.             cin >> arr[i];
    
33.         for(int i = 0; i < k; ++i)
    
34.             cin >> multiplier[i];
    
35. 
    
36.         dp = vector<vector<int>>(k+1, vector<int>(k+1, INT_MIN));
    
37. 
    
38.         int res = INT_MIN;
    
39.         // we take i elements from left, and k-i elements from right
    
40.         for(int i = 0; i <= k; ++i)
    
41.         {
    
42.             res = max(res, dfs(i, k-i));
    
43.         }
    
44.         cout << res << endl;
    
45.     }

复制代码

[/i][/i]

houghstc 发表于 2021-1-9 05:55
第一题的follow-up
[mw_shl_code=cpp,true]    int n, k;
    vector arr, multiplier;

厉害了 谢谢大佬

我不明白func是用来做什么?