diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /num_ways_remain_place.py | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'num_ways_remain_place.py')
-rw-r--r-- | num_ways_remain_place.py | 34 |
1 files changed, 34 insertions, 0 deletions
diff --git a/num_ways_remain_place.py b/num_ways_remain_place.py new file mode 100644 index 0000000..7204a3f --- /dev/null +++ b/num_ways_remain_place.py @@ -0,0 +1,34 @@ +# 1269. Number of Ways to Stay in the Same Place After Some Steps + +""" +you have a pointer at index 0 in an array of size 'arr_len'. at each step, +you can move 1 position to the left, 1 position to the right in the array, or +stay in the same plae. given two integers 'steps' and 'arr_len' return the +number of ways such that your pointer is still at index 0 after exactly +'steps' steps. since the answer may be too large, return it modulo 10e9+7 +""" + + +class Solution(object): + def dfs(self, steps, arr_len, pos): + if pos < 0 or pos >= arr_len: + return 0 + if steps == 0: + return 1 if pos == 0 else 0 + return ( + self.dfs(steps - 1, arr_len, pos - 1) + + self.dfs(steps - 1, arr_len, pos) + + self.dfs(steps - 1, arr_len, pos + 1) + ) + + def numWays(self, steps, arr_len): + if steps is None or steps < 0 or not arr_len: + return 0 + return self.dfs(steps, arr_len, 0) + + +if __name__ == "__main__": + obj = Solution() + print(obj.numWays(3, 2)) # expect: 4 + print(obj.numWays(2, 4)) # expect: 2 + print(obj.numWays(4, 2)) # expect: 8 |