算法笔试模拟题精解之“跳房子”

在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：

https://developer.aliyun.com/coding

本文为大家介绍其中的第76题：跳房子 的题目解析，具体如下：

题目描述

题目等级：中等

知识点：DP

查看题目：跳房子

给出一个长度为 n 的数组 a ，数组中的值 a[i] 表示你在第 i 个位置最多能够移动到第 i + a[i] 个位置，并且不能超过 n。你可以选择移动到的位置包括：i, i+1, ... i+a[i]。你需要确定移动到第 n 个位置的最小移动次数。如果无法移动到第 n 个位置请输出-1。

输入数组的长度n（1<=n<=100000），和含有n个数字的数组a，a[i]表示第 i 个位置最多能够移动到第 i + a[i] 个位置（0 <= a[i] <= 100）。

输出一个数字，表示最小的移动次数。

示例1

输入：

5

[2, 3, 1, 4, 5]

输出：

2

注意

最优路径为：1->2->5

解题思路：动态规划

这是一个动态规划的问题。

设f(i)为到第i个位置处的最小步数。初始化f的每个位置步数都是一个足够大的值。

Nums(i)表示第i个位置最多能够移动的距离。

对于一个位置j来说，它的最小步数应该是前面所有可以一步到达它这里的位置中最小的f(i)+1。

设f(1) = 0。后面的状态转移是 j = 1-nums(i)，f(i+j) = min( f(i)+1，f(i+j) )

空间复杂度O(n)

时间复杂度O(n^2) 每个位置都可以直接走到终点的时候。（但是可以判断是否到达终点提前结束）

看完之后是不是有了想法了呢，快来练练手吧>>