Number Of Ways To Reach A Position After Exactly K Steps

TARGET DECK: Leetcode FILE TAGS: Medium

---

Intuition

Complexity

Runtime

Space

Code

Top Down

class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        dp = {}
        def r(cur_pos, steps_used):
            if steps_used < 0:
                return 0
            if cur_pos == startPos and steps_used == 0:
                return 1
            if (cur_pos, steps_used) in dp:
                return dp[(cur_pos, steps_used)]
            
            dp[(cur_pos, steps_used)] = r(cur_pos - 1, steps_used - 1) + r(cur_pos + 1, steps_used - 1)
            return dp[(cur_pos, steps_used)]
 
        return r(endPos, k) % (10 ** 9 + 7)

Notes

Cards

START Basic Front: Number Of Ways To Reach A Position After Exactly K Steps Back:

END

---

References

• Number Of Ways To Reach A Position After Exactly K Steps