forked from lilianweng/LeetcodePython
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathjump_game.py
More file actions
58 lines (50 loc) · 1.66 KB
/
jump_game.py
File metadata and controls
58 lines (50 loc) · 1.66 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#!/usr/bin/env python
from __future__ import division
import random
'''
Leetcode: Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your *maximum* jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
'''
# DP
# R(i) = whether we can arrive at the last index from i-th element
# R(i) = R(i+1) or R(i+2) or ... or R(i+A[i])
# R(len(A)-1) = True
def jump_game(A):
n = len(A)
R = {n-1:True}
for pos in reversed(xrange(n-1)):
R[pos] = False
for next_pos in range(pos+1, min(pos+A[pos]+1, n)):
R[pos] |= R[next_pos]
print R
return R[0]
'''
Leetcode: Jump Game II
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
'''
# DP
# R(i) = minimum #steps we can arrive at the last index from i-th element (-1/None means we cannot)
# R(i) = min{R(i+1) or R(i+2) or ... or R(i+A[i])} + 1
# R(len(A)-1) = 0
def jump_game2(A):
n = len(A)
R = {n-1:0}
for pos in reversed(xrange(n-1)):
R[pos] = None
for next_pos in range(pos+1, min(pos+A[pos]+1, n)):
# Note any number > None
if (R[next_pos] >= 0) and \
((R[pos] is None) or (R[next_pos]+1 < R[pos])):
R[pos] = R[next_pos] + 1
print R
return R[0]
if __name__ == '__main__':
print jump_game2([2,3,1,1,4])
print jump_game2([3,2,1,0,4])