Java教程

算法分析:跳跃游戏

本文主要是介绍算法分析:跳跃游戏,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

  • 1.问题描述
    • 2.1贪心算法
    • 2.2动态规划
    • 3.两种算法对比

1.问题描述

给定一个非负整数数组 nums ,你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
示例 1:
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2:
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

2.1贪心算法

(1)题目分析:对于这个题目,刚开始想的是当前位置元素如果是3,我究竟是跳一步呢,还是两步呢,还是三步呢,究竟跳几步才是最优呢?然后就立马想到了能不能够通过局部最优解去获得全局的最优解。
仔细考虑一下,其实跳几步无所谓,关键在于
可跳的覆盖范围
!不一定非要明确一次究竟跳几步,每次取最大的跳跃步数,这个就是可以跳跃的覆盖范围。这个范围内,别管是怎么跳的,反正一定可以跳过来。那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点
(2)**初步思路:**每次移动取最大跳跃步数(得到最大的覆盖范围),每移动一个单位,就更新最大覆盖范围。
贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点。
局部最优推出全局最优。
图片的解释更为直观:
在这里插入图片描述
编码:

def canJump1(nums):
    cover = 0
    if len(nums) == 1: return True
    i = 0

    while i <= cover:
        cover = max(i + nums[i], cover)
        if cover >= len(nums) - 1: return True
        i += 1
    return False
a1 = [2, 3, 1, 1, 4]
a2 = [3, 2, 1, 0, 4]
print(canJump1(a1))
print(canJump1(a2))

运行结果:

True
False

2.2动态规划

(1)题目分析:通过贪心算法求解之后,可以再尝试下有没有其他方法能够解决这个问题。可以逆向思维来看一下,如果我们倒着来求,倒数第二个位置的值只有大于等于1才可以访问到最后一个值,或者倒数第三个位置的值只有大于等于2才可以访问到最后一个值。
**(2)初步思路:**定义一个end变量,作为终点,最开始的终点是len - 1。能否到达终点,就看它的:
前一个位置的数是不是大于1
或者:前两个位置的数是不是大于2
或者:前三个位置的数是不是大于3
或者:……………………(类推)
也就是nums[i] >= end - i 。如果可以的话,那么表示到了这个位置就表示可以到达终点,所以我们把这个位置定为新终点。继续看它的前一个/两个/三个/……………………
最后遍历到0,如果0是新的终点,就表示0可以到len -1。
编码:

def canJump2(nums):
    length = len(nums)
    end = length - 1
    i =length - 2
    while(i >= 0):
        if(nums[i] >= end - i ):
            end = i
        i -= 1
    return end == 0

a1 = [2, 3, 1, 1, 4]
a2 = [3, 2, 1, 0, 4]
print(canJump2(a1))
print(canJump2(a2))```
运行结果:

```python
True
False

3.两种算法对比

在本题里,贪心算法可以看作是自顶向下的求解过程,动态规划算法可以看作是自底向上的求解过程,两个算法的时间复杂度都是O(n),空间复杂度也都是O(n)。如果真要探究哪个方法更好,需要根据输入的测试数据来看,如果测试数据大多都能到达终点,则使用贪心算法的效率会相对较高,因为贪心算法在确认可以访问到最后一个终点时,就可以立即返回True,而动态规划从后往前判断,需要把所有的点都遍历一遍,从而导致效率降低。

这篇关于算法分析:跳跃游戏的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!