笔试讨论｜9.7商汤科技笔试你发挥怎么样，分享一下吧~

做商汤的不知道怎样，反正我做阿里的飘飘欲仙（

跳台阶自己的看法，我只过了65%，大佬勿喷， k说明前面k个是完全台阶，其前面的1--k个的跳法dp=2^(k-1),然后k--n的肯定是递推公式了。dp[n]=dp[n-1]+dp[n-2]...dp[n-k] 请大佬们指正！

又打扰了一家公司。。只会第二题的跳台阶，用完全背包，只过了0.5.。。。。。。

凉了。。。但是我还是想知道解法，大神们来一波题解呀

啊。编程做了一个多小时，只有第二题过了15%

n,m=[int(i) for i in input().split()] dp=[0 for j in range(n)] sum1=0 dp[0]=1 for j in range(1,m):     dp[j]=2**(j) #print(dp) for i in range(n):     if i-m>=0:         dp[i]=sum(dp[i-m:i]) print(dp[-1]%10007) 空间超了

求大佬求解答

第二道过0.7 第一道推骨牌完全没想法，感觉像是近似算法才有用吧。。。。。

//求大佬指点 不知道对不对 #include<iostream> #include<vector> using namespace std; int GetMaxScore(vector<int> &vec,vector<int> value); int main() {     int N;     while (cin >> N)     {         int Ai, Bi;         vector<int> value;         vector<int> path(N,-1);         for (int i = 0; i < N; i++)         {             cin >> Ai >> Bi;             value.push_back(Ai);             path[i] = (Bi - 1);         }         int result = GetMaxScore(path,value);         cout << result << endl;     }     return 0; } int GetMaxScore(vector<int> &vec, vector<int> value) {     vector<bool> isvisited(vec.size(), false);     int result = -99999999;     for (int i = 4; i < vec.size(); i++)     {         int j = i;         int result1 = 0;         int times = 1;         int Max = -9999;         while (vec[j] != -1 && times <= vec.size())         {             if (!isvisited[j])             {                 result1 += value[j];             }             if (result1 > Max)             {                 Max = result1;             }             j = vec[j];             times++;         }         isvisited = vector<bool>(vec.size(), false);         if (result < Max)             result = Max;     }     return result; }

围观看看有没有大佬做了第一题…

我怎么是整数操作 求极值那题

多米洛有没有老哥做出来的啊，感觉像是走递归，后面没时间了。。。

第一题不会，第二题DP时间复杂度O(n),空间复杂度O(m),运行超时只过了0.7

只有个0.7的路过。。

同求第一题算期望那题怎么做，测试用例我都没懂怎么做出来的。 第二题做了个0.75的，O(n)时间复杂度，O(m)空间复杂度，后面大数超时。有时间复杂度更低的方法么？ int64_t totalWays(int n, int m) { deque<int> dp(m, 0); dp[0] = 1; int sum = 1; for (int i = 1; i < min(n, m); ++i) { for (int j = 0; j < i; ++j) { dp[i] += dp[j]%10007; } dp[i] += 1; sum += dp[i]; sum = sum % 10007; } if (n < m) return dp[n - 1]; for (int i = m; i < n; ++i) { int front = dp.front(); dp.pop_front(); dp.push_back(sum); sum += (sum - front); sum %= 10007; if (sum < 0) sum += 10007; } return dp[m-1] % 10007; }

第一题16%

打扰了第一题极值都没做出来，明明输出正确ac还是o

研究员岗位有接到电话面试吗？是不是一周之内没有消息就凉了？