You are viewing a single comment's thread. Return to all comments →
My approach was to bottom-up fill an array A[i][j]. Where each cell represents the total number of ways you can select i elements from j possibiliities. The answer to the problem would be represented by the cell A[k-1][n-1].
The solution seems right, nevertheless I get a "Timeout Error" for the testcases 3 & 5. Is there a much more efficient way to solve that problem?
If you're computing the array each time it seems this solution would be on the O(T*n*m) ~ 10^9 which would explain why you ran out of time.
Precompute the array once for n = 1000.
Read the results for each test case out of the array.
Use a recursive function with memoization (easy for this problem)