Hi, this is Leetcode POTD. I am not looking for dp solution as there are plenty of those on leetcode. I was wondering if there's combinatorics solutions for this problem? More formally can this problem be solved for bigger constraints such as 1 <= m, n <= 1e5. If so, how can anyone provide an explanation?
Thank you for trying this problem.
Maybe it is not very fast, but you can calculate the ways that you make $$$i$$$ steps without going out by fft. Edit: Actually, we don't need fft, because we only need to know the sum of the coefficients.
To compute the 1 dimensional case, you need to know $$$\frac{\text{maxsteps}}{n}$$$ many times of answers of $$$\sum_{i=0}^y C^x_i$$$, I remember this can be done in around $$$O(T \log^2T)$$$ time, but I don't think it would be very efficient (https://www.cnblogs.com/tiatto/p/17224480.html) or (https://www.luogu.com.cn/blog/ducati/zu-ge-shuo-qian-zhui-hu-wen-ti)
In practice, The best way to compute the 1-dimensional case might be naive dp, and the time complexity is $$$O(n\times \text{maxsteps})$$$, where $$$n = \max(n, m)$$$
Well in simple terms not something that can be done by a newbie. It will take me sometime to understand. Thanks for help, much appreciated.
In fact, I said that for the 1 dimensional case, there are fancy approaches, but you can naively dp it. And the 2 dimensional case can be derived from the 1 dimensional case.
Furthermore, this is just my first thought after reading it. It is likely that there are easier and better solutions
bro don't be toxic bru
Uhh, I was not being toxic. I was saying that as I am right now it's not something I can understand easily.