LintCode Q116 Jump Game DP in Python

  • Jinhai ZHOU
  • 2 Minutes
  • 2017年1月12日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
# @param A, a list of integers
# @return a boolean
def canJump(self, A):
# write your code here
# dynamic programming
# time compmexity: O(n^2)
# space complexity: O(n)
if A is None or len(A) == 0:
return False
valide = [False]*len(A)
valide[0] = True
for i in xrange(1, len(A)):
for j in xrange(i):
if valide[j] and j + A[j] >= i:
valide[i] = True
return valide[-1]
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。