在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：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) 每个位置都可以直接走到终点的时候。（但是可以判断是否到达终点提前结束）

看完之后是不是有了想法了呢，快来练练手吧>>查看题目：跳房子