>

自由软件精神——“自由、开放、分享”。自由软件自诞生之日起,就秉承了学术自由的思想,信奉科学无国界,知识应该全人类共享。

ubuntu精神——人道待人,天下共享连接人人的信念。具有 ubuntu 精神的人心胸开阔,乐于助人,见贤思齐而不忌妒贤能......

leetcode刷题 Jump Game II

 

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.

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.)

__author__ = 'bone-lee'

class Solution:
    # @param A, a list of integers
    # @return an integer
    def jump(self, A):
        length=len(A)
        assert length>0
        inf=float('inf')
        dp=[inf]*length
        dp[0]=0
        faraway_pos=0
        i=0
        while i<=faraway_pos:
            if A[i]+i>faraway_pos:
                for k in range(faraway_pos+1,min(A[i]+i+1,length)):
                    dp[k]=dp[i]+1
                faraway_pos=A[i]+i
            if faraway_pos>=(length-1):
                return dp[-1]
            i+=1
        return -1

Meta

发布: 十二月 1, 2014

作者: Bone Lee 李智华

评论:  

字数统计: 154

下一篇: leetcode刷题 Palindrome Partitioning II

上一篇: leetcode刷题 Reverse Nodes in k-Group

Bookmark and Share

Tags

code leetcode python

comments powered by Disqus

返回顶部