最小跳跃次数

• 1. 最小跳跃次数
  
  • 1.1. 题目描述：
  • 1.2. 解题思路
  • 1.3. 实现代码

出自华为实习机试第二题：

1.1. 题目描述：

先输入一个数字代表数字总数
然后依次输入几个数字，代表当前位置能跳跃的最大步数，求到最后一个位置的最小跳跃次数。
示例
输入：
7
2
3
2
1
2
1
5
代表输入7个数，最小跳跃次数为3，可以是从2-2-2-5或者2-3-2-5，都是跳跃三次
输出为3

1.2. 解题思路

仔细阅读一下题目，可以考虑遍历搜索的方法，也可以是动态规划，用迭代的方式来做，在时间复杂度和空间复杂度上都能有优势。
将一组数记为： a0,a1,a2,...,an a 0 , a 1 , a 2 , . . . , a n ， 调到第 i i 个数的最小跳跃次数为 resi r e s i 。
则迭代公式为：

res1=0 r e s 1 = 0

resi=min(resk+1ifak−i+k>=0|k=0,...,i−1),i>1 r e s i = m i n ( r e s k + 1 i f a k − i + k >= 0 | k = 0 , . . . , i − 1 ) , i > 1

迭代结果如下：

第 i i 行的①代表 si=1 s i = 1 ，②代表 si=2 s i = 2 ，
i i 行 j j 列的数表示 resk+1 r e s k + 1 ，且满足 ak−i+k>=0 a k − i + k >= 0 即从第 i i 个数可以一步调到第 j j 个数
i i 行 j j 列的 ∗ ∗ 表示不满足 ak−i+k>=0 a k − i + k >= 0 ，即从第 i i 个数无法一步调到第 j j 个数

1.3. 实现代码

// test_huawei.cpp: 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include
using namespace std;
int main()
{
int n = 0;
cin >> n;
int numlist[n], res[n];
for (int i = 0; i {
cin >> numlist[i];
if (numlist[i] <= 0)
{
cout <<"input error";
return 0;
}
}
res[0] = 0;
int temp = INT_MAX;
for (int i = 1; i {
int temp = INT_MAX;
for (int j = 0; j {
if (numlist[j] - i + j>= 0)
{
int t = res[j] + 1;
temp = temp <= (res[j] + 1) ? temp : (res[j] + 1);
}
}
res[i] = temp;
}
cout <1] < return 0;
}