商汤科技跳台阶那题

搜下矩阵快速幂吧，这种肯定过不了大数据

你那个时间复杂度是O(mn)吧？我的时间复杂度O(n)，空间复杂度O(m)，AC 75%，显示超时 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; }

大佬们有收到面试通知的吗

你们第二题是abc吗

我这么写的过不了

只过了60%，我的递推式是f(n) = 2*f(n-1) - f(n-m-1)。之前直接申请n个地址通过50%（因为n很大，内存估计超限），然后变成申请2*m个地址，每次算完m个数就交换新的和旧的，并给n减去m直到n<m，也只通过60%。 不过是随手写的，后来看第二题通过100%也懒得继续做了。

大佬 两道通过多少啊？

static int calc(int n, int m){     if(m < 1){         return 0;     }     int mod = 10007;     int[] dp = new int[n+1];     dp[0] = 1;     for(int i=1;i<=n;i++){         int start = Math.max(i-m,0);         for(int j=start;j<=i-1;j++){            dp[i] = (dp[i] % mod + dp[j] % mod) % mod;        }     }     return dp[n] % mod; }

你通过率多少啊，还有就是i % (m + 1)是什么意思啊。。。