# 2400. Number of Ways to Reach a Position After Exactly k Steps
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/number-of-ways-to-reach-a-position-after-exactly-k-steps/
## 思路
时间序列型dp
到现在为止的number of ways只跟到旁边两个位置的number of ways有关
## Code

class Solution {
    public int numberOfWays(int startPos, int endPos, int k) {
        long[][] dp = new long[2*k+1][k+1];
        int mod = 1000000007;
        dp[k][0] = 1;
        if(Math.abs(endPos-startPos)>k) return 0;
        for(int j=1; j<=k; j++){
            for(int i=-k; i<=k; i++){
                if(Math.abs(i-1)<=k) dp[i+k][j] = (dp[i+k][j]+dp[i-1+k][j-1])%mod;
                if(Math.abs(i+1)<=k) dp[i+k][j] = (dp[i+k][j]+dp[i+1+k][j-1])%mod;;
            }
        }
        return (int)dp[endPos-startPos+k][k];
    }
}