LeetCode 2400. Number of Ways to Reach a Position After Exactly k Steps

周賽309。總算碰到和我腦波頻率相同的dp題，沒想到真正的大神竟然都是數學解，看來我還有得學。

題目

輸入兩個正整數startPos和endPos。你從startPos出發，每步可以選擇往右或往左走。
輸入正整數k，求從startPos出發走k步，到達endPos的方式有幾種。答案很大，需要模10^9+7後回傳。

注意：如果移動順序不完全相同，則兩種方式視為不同的。位置座標也可以為負數。

解法

求移動方式的計數、要對答案取餘數、測資範圍1000，這三點看下來很直覺是二維dp。

定義dp(curr,step)：目前位置為curr，已經走了step步，到達endPos的方法有幾種。
轉移方程式：只往左或是往右，dp(curr,step)=dp(curr-1,step+1)+dp(curr+1,step+1)
base cases：當走完k步時，若剛好在endPos上則回傳1，代表有一種新的方式；否則無法抵達，回傳0。

最後可以加上剪枝：當剩餘步數根本不可能從curr移動到endPos時，直接回傳0，不用浪費時間了。
順帶一提，因為可以朝兩個方向走，若改成bottom up方式的話應該要開2000*1000的矩陣，而不是1000*1000。

class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        MOD=10**9+7
        
        @cache
        def dp(curr,step):
            if step==k:
                return curr==endPos
            if abs(curr-endPos)>k-step:
                return 0
            cnt=dp(curr-1,step+1)+dp(curr+1,step+1)
            return cnt%MOD
            
        return dp(startPos,0)